Towards Quantum One-Time Memories from Stateless Hardware

Anne Broadbent1, Sevag Gharibian2,3, and Hong-Sheng Zhou3

1Department of Mathematics and Statistics, University of Ottawa, Ontario, Canada
2Department of Computer Science, Paderborn University, Germany
3Department of Computer Science, Virginia Commonwealth University, Virginia, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless ($i.e.$, reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver making at most 0.114$n$ adaptive queries to the token (for $n$ the key size), in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the "prepare-and-measure" type. We also give two impossibility results showing certain assumptions in our scheme cannot be relaxed.

In theoretical cryptography, many desirable primitives are provably impossible to implement securely. This raises a central question: What are the minimal assumptions one needs to add to the computational model in order to securely implement such primitives? In this work, the primitive we study is known as a "one-time memory (OTM)", introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008]. Briefly, an OTM hides two secret bits, so that any user of the OTM can extract precisely one of the bits; the other bit is then permanently lost. Unfortunately, secure OTMs provably do not exist in both the classical and quantum computational models. Thus, here propose the addition of a minimal assumption to the quantum computational model – that of "state-less" (i.e., reusable) hardware tokens. With this assumption in hand, we give an OTM construction which we rigorously prove is (information theoretically) secure against a malicious user making at most 0.114n (adaptive) queries to the hardware token (for n the secret key size). This security is shown in the "quantum universal composability framework", meaning our protocol composes "nicely" and securely with other primitives in this framewoek. Compared to alternative schemes, our protocol is technologically simple. We leave open the question of security against a polynomial number of queries.

► BibTeX data

► References

[1] Scott Aaronson and Paul Christiano ``Quantum Money from Hidden Subspaces'' Proc. 44th Symposium on Theory of Computing (STOC) 2012 41-60 (2012).

[2] Charles H. Bennett and Gilles Brassard ``Quantum cryptography: Public key distribution and coin tossing'' International Conference on Computers, Systems and Signal Processing 175–179 (1984).

[3] Shalev Ben-David and Or Sattath ``Quantum Tokens for Digital Signatures'' (2018) arXiv:1609.09047.

[4] Donald Beaver ``Secure Multiparty Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority'' Journal of Cryptology 4, 75–122 (1991).

[5] Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Marie-Hélène Skubiszewska, ``Practical Quantum Oblivious Transfer'' CRYPTO'91 576, 351–366 (1992).

[6] Manuel Blum, Paul Feldman, and Silvio Micali, ``Non-Interactive Zero-Knowledge and Its Applications'' 20th ACM STOC 103–112 (1988).

[7] Anne Broadbent, Gus Gutoski, and Douglas Stebila, ``Quantum One-Time Programs'' CRYPTO 2013, Part II 8043, 344–360 (2013).

[8] Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou, ``Quantum One-Time Memories from Stateless Hardware'' (2015) arXiv:1511.01363.

[9] Manuel Blum and Silvio Micali ``How to Generate Cryptographically Strong Sequences of Pseudo Random Bits'' 23rd FOCS 112–117 (1982).

[10] Anne Broadbent and Christian Schaffner ``Quantum Cryptography Beyond Quantum Key Distribution'' Designs, Codes and Cryptography 78, 351–382 (2016).

[11] Stephen Boyd and Lieven Vandenberghe ``Convex Optimization'' Cambridge University Press (2004).

[12] Ran Canetti ``Security and Composition of Multiparty Cryptographic Protocols'' Journal of Cryptology 13, 143–202 (2000).

[13] Ran Canetti ``Universally Composable Security: A New Paradigm for Cryptographic Protocols'' 42nd FOCS 136–145 (2001).

[14] Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai, ``Universally composable two-party and multi-party secure computation'' 34th ACM STOC 494–503 (2002).

[15] Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish, ``Universally Composable Security with Global Setup'' TCC 2007 4392, 61–85 (2007).

[16] Nishanth Chandran, Vipul Goyal, and Amit Sahai, ``New Constructions for UC Secure Computation Using Tamper-Proof Hardware'' EUROCRYPT 2008 4965, 545–562 (2008).

[17] Seung Geol Choi, Jonathan Katz, Dominique Schröder, Arkady Yerukhimovich, and Hong-Sheng Zhou, ``(Efficient) Universally Composable Oblivious Transfer Using a Minimal Number of Stateless Tokens'' TCC 2014 8349, 638–662 (2014).

[18] Man-Duen Choi ``Completely positive linear maps on complex matrices'' Linear Alg. Appl. 10, 285 (1975).

[19] Kai-Min Chung, Marios Georgiou, Ching-Yi Lai, and Vassilis Zikas, ``Cryptography with Disposable Backdoors'' Cryptography 3, 22 (2019).

[20] Christian Cachin and Ueli Maurer ``Unconditional security against memory-bounded adversaries'' Advances in Cryptology - CRYPTO 1997 292–306 (1997).

[21] Ivan Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner, ``Cryptography In the Bounded Quantum-Storage Model'' Symposium on Foundations of Computer Science - FOCS 2005 449–458 (2005).

[22] Ivan Damgård, Serge Fehr, Carolin Lunemann, Louis Salvail, and Christian Schaffner, ``Improving the Security of Quantum Protocols via Commit-and-Open'' CRYPTO 2009 5677, 408–427 (2009).

[23] Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail, ``Secure Two-Party Quantum Evaluation of Unitaries against Specious Adversaries'' Advances in Cryptology – Proc. CRYPTO 2010 685–706 (2010).

[24] Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail, ``Actively Secure Two-Party Evaluation of Any Quantum Operation'' Advances in Cryptology – Proc. CRYPTO 2012 7417, 794–811 (2012).

[25] Ivan Damgård and Alessandra Scafuro ``Unconditionally Secure and Universally Composable Commitments from Physical Assumptions'' ASIACRYPT 2013, Part II 8270, 100–119 (2013).

[26] Serge Fehr, Jonathan Katz, Fang Song, Hong-Sheng Zhou, and Vassilis Zikas, ``Feasibility and Completeness of Cryptographic Tasks in the Quantum World'' TCC 2013 7785, 281–296 (2013).

[27] Bill Fefferman and Shelby Kimmel ``Quantum vs. Classical Proofs and Subset Verification'' 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) 117, 22:1–22:23 (2018).

[28] Dmitry Gavinsky ``Quantum Money with Classical Verification'' Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on 42–52 (2012).

[29] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum, ``One-Time Programs'' CRYPTO 2008 5157, 39–56 (2008).

[30] Shafi Goldwasser and Leonid A. Levin ``Fair Computation of General Functions in Presence of Immoral Majority'' CRYPTO'90 537, 77–93 (1991).

[31] Oded Goldreich, Silvio Micali, and Avi Wigderson, ``How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority'' 19th ACM STOC 218–229 (1987).

[32] Vipul Goyal, Yuval Ishai, Amit Sahai, Ramarathnam Venkatesan, and Akshay Wadia, ``Founding Cryptography on Tamper-Proof Hardware Tokens'' TCC 2010 5978, 308–326 (2010).

[33] Gus Gutoski and John Watrous ``Toward a general theory of quantum games'' Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007) 565–574 (2007).

[34] Werner Heisenberg ``Schwankungserscheinungen und Quantenmechanik'' Zeitschrift fuer Physik 40, 501–506 (1927).

[35] Sean Hallgren, Adam Smith, and Fang Song, ``Classical Cryptographic Protocols in a Quantum World'' CRYPTO 2011 6841, 411–428 (2011).

[36] Yuval Ishai, Manoj Prabhakaran, and Amit Sahai, ``Founding Cryptography on Oblivious Transfer - Efficiently'' CRYPTO 2008 5157, 572–591 (2008).

[37] Andrzej Jamiołkowski ``Linear Transformations which preserve trace and positive semi-definiteness of operators'' Rep. Math. Phys. 3, 275 (1972).

[38] Jonathan Katz ``Universally Composable Multi-party Computation Using Tamper-Proof Hardware'' EUROCRYPT 2007 4515, 115–128 (2007).

[39] Joe Kilian ``Founding Cryptography on Oblivious Transfer'' 20th ACM STOC 20–31 (1988).

[40] Daniel Kraschewski and Jörn Müller-Quade ``Completeness Theorems with Constructive Proofs for Finite Deterministic 2-Party Functions'' TCC 2011 6597, 364–381 (2011).

[41] Daniel Kraschewski, Hemanta K. Maji, Manoj Prabhakaran, and Amit Sahai, ``A Full Characterization of Completeness for Two-Party Randomized Function Evaluation'' EUROCRYPT 2014 8441, 659–676 (2014).

[42] Yi-Kai Liu ``Building one-time memories from isolated qubits'' ITCS 2014 269–286 (2014).

[43] Yi-Kai Liu ``Single-Shot Security for One-Time Memories in the Isolated Qubits Model'' CRYPTO 2014, Part II 8617, 19–36 (2014).

[44] Yi-Kai Liu ``Privacy Amplification in the Isolated Qubits Model'' EUROCRYPT 2015, Part II 9057, 785–814 (2015).

[45] Huijia Lin, Rafael Pass, and Muthuramakrishnan Venkitasubramaniam, ``A unified framework for concurrent security: universal composability from stand-alone non-malleability'' 41st ACM STOC 179–188 (2009).

[46] Ueli M. Maurer ``Protocols for Secret Key Agreement by Public Discussion Based on Common Information'' Advances in Cryptology - CRYPTO 1992 740, 461–470 (1992).

[47] Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek, ``Complexity of Multi-party Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation'' TCC 2009 5444, 256–273 (2009).

[48] Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek, ``A Zero-One Law for Cryptographic Complexity with Respect to Computational UC Security'' CRYPTO 2010 6223, 595–612 (2010).

[49] Ueli Maurer and Renato Renner ``Abstract Cryptography'' ICS 2011 1–21 (2011).

[50] Silvio Micali and Phillip Rogaway ``Secure Computation (Abstract)'' CRYPTO'91 576, 392–404 (1992).

[51] Abel Molina, Thomas Vidick, and John Watrous, ``Optimal Counterfeiting Attacks and Generalizations for Wiesner’s Quantum Money'' Theory of Quantum Computation, Communication, and Cryptography 7582, 45–64 (2013).

[52] M. A. Nielsen and I. L. Chuang ``Quantum Computation and Quantum Information'' Cambridge University Press (2000).

[53] Fernando Pastawski, Norman Y Yao, Liang Jiang, Mikhail D Lukin, and J Ignacio Cirac, ``Unforgeable noise-tolerant quantum tokens'' Proceedings of the National Academy of Sciences 109, 16079 –16082 (2012).

[54] Manoj Prabhakaran and Mike Rosulek ``Cryptographic Complexity of Multi-Party Computation Problems: Classifications and Separations'' CRYPTO 2008 5157, 262–279 (2008).

[55] Manoj Prabhakaran and Amit Sahai ``New notions of security: Achieving universal composability without trusted setup'' 36th ACM STOC 242–251 (2004).

[56] Birgit Pfitzmann and Michael Waidner ``A model for asynchronous reactive systems and its application to secure message transmission'' Proc. 22nd IEEE Symposium on Security & Privacy (S&P) 2001 184–200 (2001).

[57] Marco Túlio Quintino, Qingxiuxiong Dong, Atsushi Shimbo, Akihito Soeda, and Mio Murao, ``Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations'' Phys. Rev. Lett. 123, 210502 (2019).

[58] Renato Renner ``Security of Quantum Key Distribution'' thesis (2008).

[59] Dominique Unruh ``Universally Composable Quantum Multi-party Computation'' EUROCRYPT 2010 6110, 486–505 (2010).

[60] Dominique Unruh ``Everlasting Multi-party Computation'' CRYPTO 2013, Part II 8043, 380–397 (2013).

[61] Dominique Unruh ``Revocable Quantum Timed-Release Encryption'' EUROCRYPT 2014 8441, 129–146 (2014).

[62] John Watrous ``Lecture 7: Semidefinite programming'' (2011) Latest version available at: https:/​/​​ watrous/​TQI-notes/​.

[63] Stephen Wiesner ``Conjugate coding'' ACM SIGACT News 15, 78–88 (1983) Original article written circa 1970.

[64] Andreas Winter ``Coding theorem and strong converse for quantum channels'' IEEE Transactions on Information Theory 45, 2481–2485 (1999).

[65] Stephanie Wehner, Christian Schaffner, and Barbara M. Terhal, ``Cryptography from Noisy Storage'' Physical Review Letters 100, 220502 (2008).

[66] Stephanie Wehner and Andreas Winter ``Entropic uncertainty relations—a survey'' New J. Phys. 12, 025009 (2010).

[67] William K. Wootters and Wojciech H. Zurek ``A single quantum cannot be cloned'' Nature 299, 802–803 (1982).

[68] Andrew Chi-Chih Yao ``Theory and Applications of Trapdoor Functions'' 23rd FOCS 80–91 (1982).

Cited by

[1] Sourav Kundu and Ben Reichardt, "One-time memory from isolated Majorana islands", New Journal of Physics 24 12, 123035 (2022).

[2] Yi-Kai Liu and Dustin Moody, "Post-quantum cryptography and the quantum future of cybersecurity", Physical Review Applied 21 4, 040501 (2024).

[3] Or Sattath, "Uncloneable Cryptography", Communications of the ACM 66 11, 78 (2023).

[4] Or Sattath, "Uncloneable Cryptography", arXiv:2210.14265, (2022).

[5] Amit Behera, Or Sattath, and Uriel Shinar, "Noise-Tolerant Quantum Tokens for MAC", arXiv:2105.05016, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-21 17:09:32) and SAO/NASA ADS (last updated successfully 2024-05-21 17:09:33). The list may be incomplete as not all publishers provide suitable and complete citation data.