Covert Computation in Self-Assembled Circuits
Covert Computation in Self-Assembled Circuits
复制标题
DOI：
10.1007/s00453-020-00764-w
复制
发表时间：
2019-08
期刊：
影响因子：
1.1
通讯作者：
Angel A. Cantu;Austin Luchsinger;R. Schweller;Tim Wylie
中科院分区：
文献类型：
--
作者：
Angel A. Cantu;Austin Luchsinger;R. Schweller;Tim Wylie
传统上，自组装模型中的计算很难隐藏，因为自组装过程会生成一个晶体组件，其计算历史是结构本身的固有部分。由于无法从计算中删除信息，这种计算模型提供了一个独特的问题：如何在计算和报告最终输出的同时隐藏计算输入和计算？设计这样的系统本质上是出于生物医学计算和密码学应用中的隐私问题。在本文中，我们提出了在瓷砖自组装，旨在设计自组装系统，“隐藏”的输入和计算历史的执行计算内执行“隐蔽计算”的问题。我们实现这些结果的增长限制抽象瓦片组装模型（aTAM）的积极和消极的相互作用。我们表明，一般情况下的隐蔽计算是可能的，通过实现一组基本的隐蔽逻辑门能够模拟任何电路（功能完整）。为了进一步激发隐蔽计算的研究，我们应用我们的新框架来解决一个突出的复杂性问题;我们使用我们的隐蔽电路来表明，在具有负相互作用的仅增长aTAM内的独特的组装验证问题是CONP完全的。
Traditionally, computation within self-assembly models is hard to conceal because the self-assembly process generates a crystalline assembly whose computational history is inherently part of the structure itself. With no way to remove information from the computation, this computational model offers a unique problem: how can computational input and computation be hidden while still computing and reporting the final output? Designing such systems is inherently motivated by privacy concerns in biomedical computing and applications in cryptography. In this paper we propose the problem of performing “covert computation” within tile self-assembly that seeks to design self-assembly systems that “conceal” both the input and computational history of performed computations. We achieve these results within the growth-only restricted abstract Tile Assembly Model (aTAM) with positive and negative interactions. We show that general-case covert computation is possible by implementing a set of basic covert logic gates capable of simulating any circuit (functionally complete). To further motivate the study of covert computation, we apply our new framework to resolve an outstanding complexity question; we use our covert circuitry to show that the unique assembly verification problem within the growth-only aTAM with negative interactions is coNP-complete.