Towards Quantum One-Time Memories From Stateless Hardware

Anne Broadbent¹, Sevag Gharibian^2,3, and Hong-Sheng Zhou³

¹Department of Mathematics and Statistics, University of Ottawa, Ontario, Canada
²Department of Computer Science, Paderborn University, Germany
³Department of Computer Science, Virginia Commonwealth University, Virginia, USA

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

Abstract

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.

Popular summary

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

@article{Broadbent2021towardsquantumone, doi = {10.22331/q-2021-04-08-429}, url = {https://doi.org/10.22331/q-2021-04-08-429}, title = {Towards {Q}uantum {O}ne-{T}ime {M}emories from {S}tateless {H}ardware}, author = {Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {5}, pages = {429}, month = apr, year = {2021}<br /> }

► References

[1] Scott Aaronson and Paul Christiano “Quantum Money from Hidden Subspaces” Proc. 44th Symposium on Theory of Computing (STOC) 2012 41-60 (2012).
https://doi.org/10.1145/2213977.2213983

[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).
https://doi.org/10.1016/j.tcs.2014.05.025

[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).
https://doi.org/10.1007/BF00196771

[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).
https://doi.org/10.1145/62212.62222

[7] Anne Broadbent, Gus Gutoski, and Douglas Stebila, “Quantum One-Time Programs” CRYPTO 2013, Part II 8043, 344–360 (2013).
https://doi.org/10.1007/978-3-642-40084-1_20

[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).
https://doi.org/10.1137/0213053

[10] Anne Broadbent and Christian Schaffner “Quantum Cryptography Beyond Quantum Key Distribution” Designs, Codes and Cryptography 78, 351–382 (2016).
https://doi.org/10.1007/s10623-015-0157-4

[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).
https://doi.org/10.1007/s001459910006

[13] Ran Canetti “Universally Composable Security: A New Paradigm for Cryptographic Protocols” 42nd FOCS 136–145 (2001).
https://doi.org/10.1109/SFCS.2001.959888

[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).
https://doi.org/10.1145/509907.509980

[15] Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish, “Universally Composable Security with Global Setup” TCC 2007 4392, 61–85 (2007).
https://doi.org/10.1007/978-3-540-70936-7_4

[16] Nishanth Chandran, Vipul Goyal, and Amit Sahai, “New Constructions for UC Secure Computation Using Tamper-Proof Hardware” EUROCRYPT 2008 4965, 545–562 (2008).
https://doi.org/10.5555/1788414.1788445

[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).
https://doi.org/10.1007/978-3-642-54242-8_27

[18] Man-Duen Choi “Completely positive linear maps on complex matrices” Linear Alg. Appl. 10, 285 (1975).
https://doi.org/10.1016/0024-3795(75)90075-0

[19] Kai-Min Chung, Marios Georgiou, Ching-Yi Lai, and Vassilis Zikas, “Cryptography with Disposable Backdoors” Cryptography 3, 22 (2019).
https://doi.org/10.3390/cryptography3030022

[20] Christian Cachin and Ueli Maurer “Unconditional security against memory-bounded adversaries” Advances in Cryptology – CRYPTO 1997 292–306 (1997).
https://doi.org/10.1007/BFb0052243

[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).
https://doi.org/10.1109/SFCS.2005.30

[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).
https://doi.org/10.1007/978-3-642-03356-8_24

[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).
https://doi.org/10.1007/978-3-642-14623-7_37

[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).
https://doi.org/10.1007/978-3-642-32009-5_46

[25] Ivan Damgård and Alessandra Scafuro “Unconditionally Secure and Universally Composable Commitments from Physical Assumptions” ASIACRYPT 2013, Part II 8270, 100–119 (2013).
https://doi.org/10.1007/978-3-642-42045-0_6

[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).
https://doi.org/10.1007/978-3-642-36594-2_16

[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).
https://doi.org/10.4230/LIPIcs.MFCS.2018.22

[28] Dmitry Gavinsky “Quantum Money with Classical Verification” Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on 42–52 (2012).
https://doi.org/10.1109/CCC.2012.10

[29] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum, “One-Time Programs” CRYPTO 2008 5157, 39–56 (2008).
https://doi.org/10.1007/978-3-540-85174-5_3

[30] Shafi Goldwasser and Leonid A. Levin “Fair Computation of General Functions in Presence of Immoral Majority” CRYPTO’90 537, 77–93 (1991).
https://doi.org/10.1007/3-540-38424-3_6

[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).
https://doi.org/10.1145/3335741.3335755

[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).
https://doi.org/10.1007/978-3-642-11799-2_19

[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).
https://doi.org/10.1145/1250790.1250873

[34] Werner Heisenberg “Schwankungserscheinungen und Quantenmechanik” Zeitschrift fuer Physik 40, 501–506 (1927).
https://doi.org/10.1007/BF01440827

[35] Sean Hallgren, Adam Smith, and Fang Song, “Classical Cryptographic Protocols in a Quantum World” CRYPTO 2011 6841, 411–428 (2011).
https://doi.org/10.1007/978-3-642-22792-9_23

[36] Yuval Ishai, Manoj Prabhakaran, and Amit Sahai, “Founding Cryptography on Oblivious Transfer – Efficiently” CRYPTO 2008 5157, 572–591 (2008).
https://doi.org/10.1007/978-3-540-85174-5_32

[37] Andrzej Jamiołkowski “Linear Transformations which preserve trace and positive semi-definiteness of operators” Rep. Math. Phys. 3, 275 (1972).
https://doi.org/10.1016/0034-4877(72)90011-0

[38] Jonathan Katz “Universally Composable Multi-party Computation Using Tamper-Proof Hardware” EUROCRYPT 2007 4515, 115–128 (2007).
https://doi.org/10.1007/978-3-540-72540-4_7

[39] Joe Kilian “Founding Cryptography on Oblivious Transfer” 20th ACM STOC 20–31 (1988).
https://doi.org/10.1145/62212.62215

[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).
https://doi.org/10.1007/978-3-642-19571-6_22

[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).
https://doi.org/10.1007/978-3-642-55220-5_36

[42] Yi-Kai Liu “Building one-time memories from isolated qubits” ITCS 2014 269–286 (2014).
https://doi.org/10.1145/2554797.2554823

[43] Yi-Kai Liu “Single-Shot Security for One-Time Memories in the Isolated Qubits Model” CRYPTO 2014, Part II 8617, 19–36 (2014).
https://doi.org/10.1007/978-3-662-44381-1_2

[44] Yi-Kai Liu “Privacy Amplification in the Isolated Qubits Model” EUROCRYPT 2015, Part II 9057, 785–814 (2015).
https://doi.org/10.1007/978-3-662-46803-6_26

[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).
https://doi.org/10.1145/1536414.1536441

[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).
https://doi.org/10.1007/3-540-48071-4_32

[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).
https://doi.org/10.1007/978-3-642-00457-5_16

[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).
https://doi.org/10.1007/978-3-642-14623-7_32

[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).
https://doi.org/10.1007/3-540-46766-1_32

[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).
https://doi.org/10.1007/978-3-642-35656-8_4

[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).
https://doi.org/10.1073/pnas.1203552109

[54] Manoj Prabhakaran and Mike Rosulek “Cryptographic Complexity of Multi-Party Computation Problems: Classifications and Separations” CRYPTO 2008 5157, 262–279 (2008).
https://doi.org/10.1007/978-3-540-85174-5_15

[55] Manoj Prabhakaran and Amit Sahai “New notions of security: Achieving universal composability without trusted setup” 36th ACM STOC 242–251 (2004).
https://doi.org/10.1145/1007352.1007394

[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).
https://doi.org/10.1109/SECPRI.2001.924298

[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).
https://doi.org/10.1103/PhysRevLett.123.210502

[58] Renato Renner “Security of Quantum Key Distribution” thesis (2008).
https://doi.org/10.1142/S0219749908003256

[59] Dominique Unruh “Universally Composable Quantum Multi-party Computation” EUROCRYPT 2010 6110, 486–505 (2010).
https://doi.org/10.1007/978-3-642-13190-5_25

[60] Dominique Unruh “Everlasting Multi-party Computation” CRYPTO 2013, Part II 8043, 380–397 (2013).
https://doi.org/10.1007/978-3-642-40084-1_22

[61] Dominique Unruh “Revocable Quantum Timed-Release Encryption” EUROCRYPT 2014 8441, 129–146 (2014).
https://doi.org/10.1007/978-3-642-55220-5_8

[62] John Watrous “Lecture 7: Semidefinite programming” (2011) Latest version available at: https://cs.uwaterloo.ca/ watrous/TQI-notes/.
https://cs.uwaterloo.ca/~watrous/TQI-notes/

[63] Stephen Wiesner “Conjugate coding” ACM SIGACT News 15, 78–88 (1983) Original article written circa 1970.
https://doi.org/10.1145/1008908.1008920

[64] Andreas Winter “Coding theorem and strong converse for quantum channels” IEEE Transactions on Information Theory 45, 2481–2485 (1999).
https://doi.org/10.1109/18.796385

[65] Stephanie Wehner, Christian Schaffner, and Barbara M. Terhal, “Cryptography from Noisy Storage” Physical Review Letters 100, 220502 (2008).
https://doi.org/10.1103/PhysRevLett.100.220502

[66] Stephanie Wehner and Andreas Winter “Entropic uncertainty relations—a survey” New J. Phys. 12, 025009 (2010).
https://doi.org/10.1088/1367-2630/12/2/025009

[67] William K. Wootters and Wojciech H. Zurek “A single quantum cannot be cloned” Nature 299, 802–803 (1982).
https://doi.org/10.1038/299802a0

[68] Andrew Chi-Chih Yao “Theory and Applications of Trapdoor Functions” 23rd FOCS 80–91 (1982).
https://doi.org/10.1109/SFCS.1982.45

Cited by

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.

Generative Data Intelligence

Towards Quantum One-Time Memories from Stateless Hardware

Abstract

Popular summary

► BibTeX data

► References

Cited by

Uncovering the Hidden Truth: Global Aviation Emissions Exceed Reported Numbers by 300 Million Metric Tons

The Secret Of Retropolis Plans Apple Vision Pro Release

Latest Intelligence

Unprecedented Floods and Landslides in Kenya: Stay Informed with EcoWatch’s Email Newsletter!

This Plastic Carries the Ingredients to Biodegrade Itself After Its Thrown Out

Dungeons Of Eternity Update Adds Longsword, bHaptics & More

Bitcoin Cash (BCH) Backer Roger Ver Arrested and Charged With Evading Nearly $50,000,000 in Taxes – The Daily Hodl

Tether’s Record $4.5 Billion Q1 Profit Highlights Its Dominance of the Stablecoin Industry – Unchained

Microsoft announces $2.2B for cloud and AI in Malaysia

Chat with us