Mark Zhandry
Skip Abstract Section
Abstract
Pseudorandom functions (PRFs) are one of the foundational concepts in theoretical computer science, with numerous applications in complexity theory and cryptography. In this work, we study the security of PRFs when evaluated on quantum superpositions of inputs. The classical techniques for arguing the security of PRFs do not carry over to this setting, even if the underlying building blocks are quantum resistant. We therefore develop a new proof technique to show that many of the classical PRF constructions remain secure when evaluated on superpositions.
- Scott Aaronson. 2009. Quantum copy-protection and quantum money. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC’09). http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5231194. Google Scholar
Digital Library
- Scott Aaronson and Paul Christiano. 2012. Quantum money from hidden subspaces. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, Howard J. Karloff and Toniann Pitassi (Eds.). ACM Press, New York, NY, 41–60. DOI:https://doi.org/10.1145/2213977.2213983 Google ScholarDigital Library
- Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. 2020. Quantum-access-secure message authentication via blind-unforgeability. In Advances in Cryptology (EUROCRYPT’20), Part III, Lecture Notes in Computer Science, Vol. 12107, Anne Canteaut and Yuval Ishai (Eds.). Springer, Heidelberg, Germany, 788–817. DOI:https://doi.org/10.1007/978-3-030-45727-3_27Google Scholar
- Gorjan Alagic and Alexander Russell. 2017. Quantum-secure symmetric-key cryptography based on hidden shifts. In Advances in Cryptology (EUROCRYPT’17), Part III, Lecture Notes in Computer Science, Vol. 10212, Jean-Sébastien Coron and Jesper Buus Nielsen (Eds.). Springer, Heidelberg, Germany, 65–93. DOI:https://doi.org/10.1007/978-3-319-56617-7_3Google Scholar
- Andris Ambainis, Ansis Rosmanis, and Dominique Unruh. 2014. Quantum attacks on classical proof systems: The hardness of quantum rewinding. In Proceedings of the 55th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Philadelphia, PA, 474–483. DOI:https://doi.org/10.1109/FOCS.2014.57 Google ScholarDigital Library
- Milton Abramowitz and Irene Stegun. 1964. Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables. Dover Publications, Inc. Google ScholarDigital Library
- Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26 (1997), 1510–1523. http://arxiv.org/abs/quant-ph/9701001. Google ScholarDigital Library
- Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. 2011. Random oracles in a quantum world. In Advances in Cryptology (ASIACRYPT’11), Lecture Notes in Computer Science, Vol. 7073, Dong Hoon Lee and Xiaoyun Wang (Eds.). Springer, Heidelberg, Germany, 41–69. DOI:https://doi.org/10.1007/978-3-642-25385-0_3 Google ScholarDigital Library
- Gilles Brassard, Peter Høyer, and Alain Tapp. 1997. Quantum algorithm for the collision problem. ACM SIGACT News (Cryptology Column) 28 (1997), 14–19. http://arxiv.org/abs/quant-ph/9705002.Google ScholarDigital Library
- Manuel Blum and Russell Impagliazzo. 1987. Generic oracles and oracle classes (extended abstract). In Proceedings of the 28th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Angeles, CA, 118–126. DOI:https://doi.org/10.1109/SFCS.1987.30 Google ScholarDigital Library
- Dan Boneh and Richard J. Lipton. 1995. Quantum cryptanalysis of hidden linear functions (extended abstract). In Advances in Cryptology (CRYPTO’95), Lecture Notes in Computer Science, Vol. 963, Don Coppersmith (Ed.). Springer, Heidelberg, Germany, 424–437. DOI:https://doi.org/10.1007/3-540-44750-4_34 Google ScholarDigital Library
- Dan Boneh, Hart William Montgomery, and Ananth Raghunathan. 2010. Algebraic pseudorandom functions with improved efficiency from the augmented cascade. In Proceedings of the 17th Conference on Computer and Communications Security (ACM CCS’10), Ehab Al-Shaer, Angelos D. Keromytis, and Vitaly Shmatikov (Eds.). ACM Press, Chicago, Illinois, 131–140. DOI:https://doi.org/10.1145/1866307.1866323 Google ScholarDigital Library
- Dan Boneh. 1998. The decision Diffie-Hellman problem. In Proceedings of the 3rd Algorithmic Number Theory Symposium (ANTS’98), Lecture Notes in Computer Science, Vol. 1423. Springer, Heidelberg, Germany. Invited paper. Google ScholarDigital Library
- Abhishek Banerjee, Chris Peikert, and Alon Rosen. 2012. Pseudorandom functions and lattices. In Advances in Cryptology (EUROCRYPT’12)Lecture Notes in Computer Science, Vol. 7237, David Pointcheval and Thomas Johansson (Eds.). Springer, Heidelberg, Germany, 719–737. DOI:https://doi.org/10.1007/978-3-642-29011-4_42 Google ScholarDigital Library
- Zvika Brakerski and Omri Shmueli. 2019. (Pseudo) random quantum states with binary phase. In Proceedings of the 17th Theory of Cryptography Conference (TCC’19), Part I, Lecture Notes in Computer Science, Vol. 11891, Dennis Hofheinz and Alon Rosen (Eds.). Springer, Heidelberg, Germany, 229–250. DOI:https://doi.org/10.1007/978-3-030-36030-6_10Google ScholarCross Ref
- Zvika Brakerski and Vinod Vaikuntanathan. 2011. Efficient fully homomorphic encryption from (standard) LWE. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, Rafail Ostrovsky (Ed.). IEEE Computer Society Press, Palm Springs, CA, 97–106. DOI:https://doi.org/10.1109/FOCS.2011.12 Google ScholarDigital Library
- Dan Boneh and Mark Zhandry. 2013. Quantum-secure message authentication codes. In Advances in Cryptology (EUROCRYPT’13)Lecture Notes in Computer Science, Vol. 7881, Thomas Johansson and Phong Q. Nguyen (Eds.). Springer, Heidelberg, Germany, 592–608. DOI:https://doi.org/10.1007/978-3-642-38348-9_35Google Scholar
- Dan Boneh and Mark Zhandry. 2013. Secure signatures and chosen ciphertext security in a quantum computing world. In Advances in Cryptology (CRYPTO’13), Part II, Lecture Notes in Computer Science, Vol. 8043, Ran Canetti and Juan A. Garay (Eds.). Springer, Heidelberg, Germany, 361–379. DOI:https://doi.org/10.1007/978-3-642-40084-1_21Google Scholar
- Jan Czajkowski, Andreas Hülsing, and Christian Schaffner. 2019. Quantum indistinguishability of random sponges. In Advances in Cryptology (CRYPTO’19), Part II, Lecture Notes in Computer Science, Vol. 11693, Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer, Heidelberg, Germany, 296–325. DOI:https://doi.org/10.1007/978-3-030-26951-7_11Google Scholar
- Ivan Damgård, Jakob Funder, Jesper Buus Nielsen, and Louis Salvail. 2014. Superposition attacks on cryptographic protocols. In Proceedings of the 7th International Conference on Information Theoretic Security (ICITS’13), Lecture Notes in Computer Science, Vol. 8317, Carles Padró (Ed.). Springer, Heidelberg, Germany, 142–161. DOI:https://doi.org/10.1007/978-3-319-04268-8_9Google ScholarCross Ref
- Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Michael Mitzenmacher (Ed.). ACM Press, 169–178. DOI:https://doi.org/10.1145/1536414.1536440 Google ScholarDigital Library
- Oded Goldreich, Shafi Goldwasser, and Silvio Micali. 1984. How to construct random functions (extended abstract). In Proceedings of the 25th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 464–479. DOI:https://doi.org/10.1109/SFCS.1984.715949 Google ScholarDigital Library
- Oded Goldreich, Shafi Goldwasser, and Silvio Micali. 1986. How to construct random functions. J. ACM 33, 4 (Oct. 1986), 792–807. Google ScholarDigital Library
- Tommaso Gagliardoni, Andreas Hülsing, and Christian Schaffner. 2016. Semantic security and indistinguishability in the quantum world. In Advances in Cryptology (CRYPTO’16), Part III, Lecture Notes in Computer Science, Vol. 9816, Matthew Robshaw and Jonathan Katz (Eds.). Springer, Heidelberg, Germany, 60–89. DOI:https://doi.org/10.1007/978-3-662-53015-3_3 Google ScholarDigital Library
- Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. 2013. Reusable garbled circuits and succinct functional encryption. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (Eds.). ACM Press, 555–564. DOI:https://doi.org/10.1145/2488608.2488678 Google ScholarDigital Library
- Rishab Goyal, Venkata Koppula, and Brent Waters. 2017. Lockable obfuscation. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science, Chris Umans (Ed.). IEEE Computer Society Press, 612–621. DOI:https://doi.org/10.1109/FOCS.2017.62Google ScholarCross Ref
- Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM Press, 212–219. DOI:https://doi.org/10.1145/237814.237866 Google ScholarDigital Library
- Akinori Hosoyamada and Tetsu Iwata. 2019. 4-round Luby-Rackoff construction is a qPRP. In Advances in Cryptology (ASIACRYPT’19), Part ILecture Notes in Computer Science, Vol. 11921, Steven D. Galbraith and Shiho Moriai (Eds.). Springer, Heidelberg, Germany, 145–174. DOI:https://doi.org/10.1007/978-3-030-34578-5_6Google Scholar
- Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. 1999. A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 4 (1999), 1364–1396. Google ScholarDigital Library
- Zhengfeng Ji, Yi-Kai Liu, and Fang Song. 2018. Pseudorandom quantum states. In Advances in Cryptology (CRYPTO’18), Part III, Lecture Notes in Computer Science, Vol. 10993, Hovav Shacham and Alexandra Boldyreva (Eds.). Springer, Heidelberg, Germany, 126–152. DOI:https://doi.org/10.1007/978-3-319-96878-0_5Google Scholar
- Jonathan Katz and Yehuda Lindell. 2014. Introduction to Modern Cryptography (2nd ed.). Chapman & Hall/CRC. Google ScholarDigital Library
- Allison B. Lewko and Brent Waters. 2009. Efficient pseudorandom functions from the decisional linear assumption and weaker variants. In Proceedings of the 16th Conference on Computer and Communications Security (ACM CCS’09), Ehab Al-Shaer, Somesh Jha, and Angelos D. Keromytis (Eds.). ACM Press, 112–120. DOI:https://doi.org/10.1145/1653662.1653677 Google ScholarDigital Library
- Michael A. Nielsen and Isaac Chuang. 2000. Quantum computation and quantum information. Am. J. Phys. 70, 5 (2000), 558. DOI:https://doi.org/10.1119/1.1463744Google ScholarCross Ref
- Moni Naor and Omer Reingold. 1995. Synthesizers and their application to the parallel construction of pseudo-random functions. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 170–181. DOI:https://doi.org/10.1109/SFCS.1995.492474 Google ScholarDigital Library
- Moni Naor and Omer Reingold. 1997. Number-theoretic constructions of efficient pseudo-random functions. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 458–467. DOI:https://doi.org/10.1109/SFCS.1997.646134 Google ScholarDigital Library
- Moni Naor, Omer Reingold, and Alon Rosen. 2000. Pseudo-random functions and factoring (extended abstract). In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. ACM Press, 11–20. DOI:https://doi.org/10.1145/335305.335307 Google ScholarDigital Library
- Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Harold N. Gabow and Ronald Fagin (Eds.). ACM Press, 84–93. DOI:https://doi.org/10.1145/1060590.1060603 Google ScholarDigital Library
- Alexander A. Razborov and Steven Rudich. 1994. Natural proofs. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing. ACM Press, 204–213. DOI:https://doi.org/10.1145/195058.195134 Google ScholarDigital Library
- Peter W. Shor. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 124–134. DOI:https://doi.org/10.1109/SFCS.1994.365700 Google ScholarDigital Library
- Fang Song and Aaram Yun. 2017. Quantum security of NMAC and related constructions—PRF domain extension against quantum attacks. In Advances in Cryptology (CRYPTO’17), Part II, Lecture Notes in Computer Science, Vol. 10402, Jonathan Katz and Hovav Shacham (Eds.). Springer, Heidelberg, Germany, 283–309. DOI:https://doi.org/10.1007/978-3-319-63715-0_10Google ScholarCross Ref
- Philipp Woelfel. 1999. Efficient strongly universal and optimally universal hashing. In Proceedings of the 24th International Symposium on Mathematical Foundations of Computer Science (MFCS’99), Lecture Notes in Computer Science, Vol. 1672. 262–272. DOI:https://doi.org/10.1007/3-540-48340-3_24 Google ScholarDigital Library
- Daniel Wichs and Giorgos Zirdelis. 2017. Obfuscating compute-and-compare programs under LWE. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science, Chris Umans (Ed.). IEEE Computer Society Press, 600–611. DOI:https://doi.org/10.1109/FOCS.2017.61Google ScholarCross Ref
- Mark Zhandry. 2012. Secure identity-based encryption in the quantum random oracle model. In Advances in Cryptology (CRYPTO’12), Lecture Notes in Computer Science, Vol. 7417, Reihaneh Safavi-Naini and Ran Canetti (Eds.). Springer, Heidelberg, Germany, 758–775. DOI:https://doi.org/10.1007/978-3-642-32009-5_44 Google ScholarDigital Library
- Mark Zhandry. 2015. A note on the quantum collision and set equality problems. Quant, Inf, Comput, 15, 7& 8 (2015). Full version available at http://arxiv.org/abs/1312.1027. Google ScholarDigital Library
- Mark Zhandry. 2016. The Magic of ELFs. Cryptology ePrint Archive, Report 2016/114. https://eprint.iacr.org/2016/114.Google Scholar
- Mark Zhandry. 2016. A Note on Quantum-Secure PRPs. Cryptology ePrint Archive, Report 2016/1076. https://eprint.iacr.org/2016/1076.Google Scholar
Index Terms
- How to Construct Quantum Random Functions
Recommendations
How to Construct Quantum Random Functions
FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer ScienceIn the presence of a quantum adversary, there are two possible definitions of security for a pseudorandom function. The first, which we call standard-security, allows the adversary to be quantum, but requires queries to the function to be classical. The ...
Secure Identity-Based Encryption in the Quantum Random Oracle Model
Proceedings of the 32nd Annual Cryptology Conference on Advances in Cryptology --- CRYPTO 2012 - Volume 7417We give the first proof of security for an identity-based encryption scheme in the quantum random oracle model. This is the first proof of security for any scheme in this model that requires no additional assumptions. Our techniques are quite general ...
Efficient Selective Identity-Based Encryption Without Random Oracles
We construct two efficient Identity-Based Encryption (IBE) systems that admit selective-identity security reductions without random oracles in groups equipped with a bilinear map. Selective-identity secure IBE is a slightly weaker security model than ...
Comments