License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.31
URN: urn:nbn:de:0030-drops-106075
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10607/
Go to the corresponding LIPIcs Volume Portal

Cantu, Angel A. ; Luchsinger, Austin ; Schweller, Robert ; Wylie, Tim

Covert Computation in Self-Assembled Circuits

pdf-format:
LIPIcs-ICALP-2019-31.pdf (2 MB)

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.

BibTeX - Entry

@InProceedings{cantu_et_al:LIPIcs:2019:10607,
  author =	{Angel A. Cantu and Austin Luchsinger and Robert Schweller and Tim Wylie},
  title =	{{Covert Computation in Self-Assembled Circuits}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10607},
  URN =		{urn:nbn:de:0030-drops-106075},
  doi =		{10.4230/LIPIcs.ICALP.2019.31},
  annote =	{Keywords: self-assembly, covert circuits}
}

Keywords: self-assembly, covert circuits
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI