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.
 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).
 Shalev Ben-David and Or Sattath ``Quantum Tokens for Digital Signatures'' (2018) arXiv:1609.09047.
 Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Marie-Hélène Skubiszewska, ``Practical Quantum Oblivious Transfer'' CRYPTO'91 576, 351–366 (1992).
 Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou, ``Quantum One-Time Memories from Stateless Hardware'' (2015) arXiv:1511.01363.
 Stephen Boyd and Lieven Vandenberghe ``Convex Optimization'' Cambridge University Press (2004).
 Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai, ``Universally composable two-party and multi-party secure computation'' 34th ACM STOC 494–503 (2002).
 Nishanth Chandran, Vipul Goyal, and Amit Sahai, ``New Constructions for UC Secure Computation Using Tamper-Proof Hardware'' EUROCRYPT 2008 4965, 545–562 (2008).
 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).
 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).
 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).
 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).
 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).
 Ivan Damgård and Alessandra Scafuro ``Unconditionally Secure and Universally Composable Commitments from Physical Assumptions'' ASIACRYPT 2013, Part II 8270, 100–119 (2013).
 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).
 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).
 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).
 Vipul Goyal, Yuval Ishai, Amit Sahai, Ramarathnam Venkatesan, and Akshay Wadia, ``Founding Cryptography on Tamper-Proof Hardware Tokens'' TCC 2010 5978, 308–326 (2010).
 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).
 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).
 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).
 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).
 Ueli M. Maurer ``Protocols for Secret Key Agreement by Public Discussion Based on Common Information'' Advances in Cryptology - CRYPTO 1992 740, 461–470 (1992).
 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).
 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).
 Ueli Maurer and Renato Renner ``Abstract Cryptography'' ICS 2011 1–21 (2011).
 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).
 M. A. Nielsen and I. L. Chuang ``Quantum Computation and Quantum Information'' Cambridge University Press (2000).
 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).
 Manoj Prabhakaran and Mike Rosulek ``Cryptographic Complexity of Multi-Party Computation Problems: Classifications and Separations'' CRYPTO 2008 5157, 262–279 (2008).
 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).
 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).
 Stephanie Wehner, Christian Schaffner, and Barbara M. Terhal, ``Cryptography from Noisy Storage'' Physical Review Letters 100, 220502 (2008).
 Stephanie Wehner and Andreas Winter ``Entropic uncertainty relations—a survey'' New J. Phys. 12, 025009 (2010).
 Sourav Kundu and Ben Reichardt, "One-time memory from isolated Majorana islands", New Journal of Physics 24 12, 123035 (2022).
 Or Sattath, "Uncloneable Cryptography", Communications of the ACM 66 11, 78 (2023).
The above citations are from Crossref's cited-by service (last updated successfully 2023-12-07 04:39:43) and SAO/NASA ADS (last updated successfully 2023-12-07 04:39:44). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.