Document Open Access Logo

Covert Computation in Self-Assembled Circuits

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.31.pdf
  • Filesize: 1.61 MB
  • 14 pages

Document Identifiers

Author Details

Angel A. Cantu
  • Department of Computer Science, University of Texas - Rio Grande Valley, USA
Austin Luchsinger
  • Department of Computer Science, University of Texas - Rio Grande Valley, USA
Robert Schweller
  • Department of Computer Science, University of Texas - Rio Grande Valley, USA
Tim Wylie
  • Department of Computer Science, University of Texas - Rio Grande Valley, USA

Funding

This research was supported in part by National Science Foundation Grant CCF-1817602.

Acknowledgements

We would like to thank the anonymous reviewers for their careful review of our work and for their constructive feedback.

Cite AsGet BibTex

Angel A. Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie. Covert Computation in Self-Assembled Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.31

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • self-assembly
  • covert circuits

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espanés, and Paul W. K. Rothemund. Combinatorial optimization problems in self-assembly. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 23-32, 2002. Google Scholar
  2. Yuriy Brun. Arithmetic computation in the tile assembly model: Addition and multiplication. Theoretical Comp. Sci., 378:17-31, 2007. Google Scholar
  3. Cameron Chalk, Erik D. Demiane, Martin L. Demaine, Eric Martinez, Robert Schweller, Luis Vega, and Tim Wylie. Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces. In Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), 2017. Google Scholar
  4. Cameron Chalk, Austin Luchsinger, Robert Schweller, and Tim Wylie. Self-Assembly of Any Shape with Constant Tile Types using High Temperature. In Proc. of the 26th Annual European Symposium on Algorithms, ESA'18, 2018. Google Scholar
  5. David Chaum, Claude Crépeau, and Ivan Bjerre Damgård. Multiparty Unconditionally Secure Protocols (Abstract). In Proc. of the 20th Annual ACM Symposium on Theory of Computing (STOC'88), pages 11-19, 1988. Google Scholar
  6. Peter Claes, Denise K. Liberton, and Katleen et al. Daniels. Modeling 3D Facial Shape from DNA. PLOS Genetics, 10(3):1-14, March 2014. URL: http://dx.doi.org/10.1371/journal.pgen.1004224.
  7. Emiliano De Cristofaro, Sky Faber, and Gene Tsudik. Secure Genomic Testing with Size- and Position-hiding Private Substring Matching. In Proc. of the 12th ACM Workshop on Privacy in the Electronic Society, WPES'13, pages 107-118. ACM, 2013. Google Scholar
  8. David Doty. Theory of Algorithmic Self-Assembly. Communications of the ACM, 55(12):78-88, 2012. Google Scholar
  9. David Doty, Lila Kari, and Benoît Masson. Negative Interactions in Irreversible Self-assembly. Algorithmica, 66(1):153-172, 2013. Google Scholar
  10. David Doty, Jack H. Lutz, Matthew J. Patitz, Robert Schweller, Scott M. Summers, and Damien Woods. The Tile Assembly Model is Intrinsically Universal. In Proc. of the 53rd IEEE Conf. on Foun. of Comp. Sci., FOCS '12, 2012. Google Scholar
  11. N. Dowlin, R. Gilad-Bachrach, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing. Manual for Using Homomorphic Encryption for Bioinformatics. Proceedings of the IEEE, 105(3):552-567, March 2017. Google Scholar
  12. Constantine Evans. Crystals that Count! Physical Principles and Experimental Investigations of DNA Tile Self-Assembly. PhD thesis, California Inst. of Tech., 2014. Google Scholar
  13. Melissa Gymrek, Amy L. McGuire, David Golan, Eran Halperin, and Yaniv Erlich. Identifying Personal Genomes by Surname Inference. Science, 339(6117):321-324, 2013. Google Scholar
  14. Z. Huang, E. Ayday, J. Fellay, J. Hubaux, and A. Juels. GenoGuard: Protecting Genomic Data against Brute-Force Attacks. In 2015 IEEE Symposium on Security and Privacy, pages 447-462, May 2015. URL: http://dx.doi.org/10.1109/SP.2015.34.
  15. Alexandra Keenan, Robert Schweller, Michael Sherman, and Xingsi Zhong. Fast arithmetic in algorithmic self-assembly. Natural Computing, 15(1):115-128, March 2016. Google Scholar
  16. Eric S. Lander, Lauren M. Linton, and Bruce Birren et al. Initial sequencing and analysis of the human genome. Nature, 409(6822):860-921, February 2001. Google Scholar
  17. Austin Luchsinger, Robert Schweller, and Tim Wylie. Self-assembly of shapes at constant scale using repulsive forces. Natural Computing, August 2018. URL: http://dx.doi.org/10.1007/s11047-018-9707-9.
  18. Matthew J. Patitz. An introduction to tile-based self-assembly and a survey of recent results. Natural Computing, 13(2):195-224, June 2014. Google Scholar
  19. Matthew J. Patitz, Trent A. Rogers, Robert Schweller, Scott M. Summers, and Andrew Winslow. Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly. In Proc. of DNA Computing and Molecular Programming, DNA'16, pages 98-113, 2016. Google Scholar
  20. Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers. Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue. In DNA Comp. and Molecular Prog., volume 6937 of LNCS, pages 175-189. Springer, 2011. Google Scholar
  21. John H. Reif, Sudheer Sahu, and Peng Yin. Complexity of graph self-assembly in accretive systems and self-destructible systems. Theoretical Comp. Sci., 412(17):1592-1605, 2011. Google Scholar
  22. Robert Schweller and Michael Sherman. Fuel Efficient Computation in Passive Self-Assembly. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'13, pages 1513-1525. SIAM, 2013. Google Scholar
  23. Allan Scott, Ulrike Stege, and Iris van Rooij. Minesweeper May Not Be NP-Complete but Is Hard Nonetheless. The Mathematical Intelligencer, 33(4):5-17, December 2011. Google Scholar
  24. Heribert Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag, Berlin, Heidelberg, 1999. Google Scholar
  25. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, June 1998. Google Scholar
  26. Jing Yang, Jingjing Ma, Shi Liu, and Cheng Zhang. A molecular cryptography model based on structures of DNA self-assembly. Chinese Science Bulletin, 59(11):1192-1198, April 2014. URL: http://dx.doi.org/10.1007/s11434-014-0170-4.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact