Covert Computation in Self-Assembled Circuits
- PDF / 1,781,352 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 82 Downloads / 191 Views
Covert Computation in Self‑Assembled Circuits Angel A. Cantu1 · Austin Luchsinger1 · Robert Schweller1 · Tim Wylie1 Received: 27 January 2020 / Accepted: 24 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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. Keywords Self-assembly · Covert computation · Atam
* Tim Wylie [email protected] Angel A. Cantu [email protected] Austin Luchsinger [email protected] Robert Schweller [email protected] 1
University of Texas - Rio Grande Valley, Edinburg, TX, USA
13
Vol.:(0123456789)
Algorithmica
1 Introduction Since the discovery of DNA over half a century ago, humans have been continually working to understand and harness the vast amount of information it contains. The Human Genome Project [19], which began in 1990 and took a decade, was the first major attempt to fully sequence the human genome. In the years since, sequencing has become extremely cheap and easy, and our ability to manipulate DNA has emerged as a central tool for many applications related to nanotechnology and biomedical engineering. Although this progress has many benefits, as we learn more about the information, we also must be careful with the shared data. There are databases of anonymous DNA sequences, which can sometimes be deanonymized with only small amounts of information such as a surname [16], or by reconstructing physical features from the DNA [8]. In order to address these issues, there has been work on cryptographic schemes aimed at obscuring results related to DNA or the input/output [9, 13, 17, 30]. In this work we take the first steps in addressing some of these issues within selfassembling systems by proposing a new style of co
Data Loading...
