On Quantum Simulation-Soundness
Authors
Behzad Abdolmaleki, Céline Chevalier, Ehsan Ebrahimi, Giulio Malavolta, Quoc-Huy Vu
Behzad Abdolmaleki
University of Sheffield, Sheffield, UK
behzad dot abdolmaleki at sheffield dot ac dot uk
behzad dot abdolmaleki at sheffield dot ac dot uk
Céline Chevalier
CRED, Université Panthéon-Assas, Paris II, Paris, France
DIENS, École normale supérieure, PSL University, CNRS, INRIA, Paris, France
celine dot chevalier at ens dot fr
DIENS, École normale supérieure, PSL University, CNRS, INRIA, Paris, France
celine dot chevalier at ens dot fr
Ehsan Ebrahimi
University of Luxembourg, Luxembourg
eebrahimi dot pqc at gmail dot com
eebrahimi dot pqc at gmail dot com
Giulio Malavolta
Bocconi University, Milan, Italy
Max-Planck Institute in Security and Privacy, Bochum, Germany
giulio dot malavolta at hotmail dot it
Max-Planck Institute in Security and Privacy, Bochum, Germany
giulio dot malavolta at hotmail dot it
Quoc-Huy Vu
Léonard de Vinci Pôle Universitaire, Research Center, Paris La Défense, France
quoc dot huy dot vu at ens dot fr
quoc dot huy dot vu at ens dot fr
Abstract
Non-interactive zero-knowledge (NIZK) proof systems are a cornerstone of modern cryptography, but their security has received little attention in the quantum settings. Motivated by improving our understanding of this fundamental primitive against quantum adversaries, we propose a new definition of security against quantum adversary. Specifically, we define the notion of quantum simulation soundness (SS-NIZK), that allows the adversary to access the simulator in superposition.
We show a separation between post-quantum and quantum security of SS-NIZK, and prove that Sahai’s construction for SS-NIZK (in the CRS model) can be made quantumly-simulation-sound. As an immediate application of our new notion, we prove the security of the Naor-Yung paradigm in the quantum settings, with respect to a strong quantum IND-CCA security notion. This provides the quantum analogue of the classical dual key approach to prove the security of encryption schemes. Along the way, we introduce a new notion of quantum-query advantage functions, which may be used as a general framework to show classical/quantum separation for other cryptographic primitives, and it may be of independent interest.
References
[ABKM22]
Gorjan Alagic, Chen Bai, Jonathan Katz, and Christian Majenz. Post-Quantum Security of the Even-Mansour Cipher. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part III, volume 13277 of LNCS, pages 458–487. 2022. Springer, Heidelberg. DOI: 10.1007/978-3-031-07082-2_17
[AGRS24]
Behzad Abdolmaleki, Noemi Glaeser, Sebastian Ramacher, and Daniel Slamanig. Circuit-Succinct Universally-Composable NIZKs with Updatable CRS. In 37th IEEE Computer Security Foundations Symposium, CSF 2024, Enschede, Netherlands, July 8-12, 2024, pages 527–542. 2024. IEEE. DOI: 10.1109/CSF61375.2024.00006
[AMRS20]
Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. Quantum-Access-Secure Message Authentication via Blind-Unforgeability. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 788–817. May 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-45727-3_27
[AMRS23]
Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. Quantum-secure message authentication via blind-unforgeability. arXiv preprint arXiv:1803.03761v4, 2023.
[ARS20]
Behzad Abdolmaleki, Sebastian Ramacher, and Daniel Slamanig. Lift-and-Shift: Obtaining Simulation Extractable Subversion and Updatable SNARKs Generically. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 2020, pages 1987–2005. November 2020. ACM Press. DOI: 10.1145/3372297.3417228
[ATTU16]
Mayuresh Vivekanand Anand, Ehsan Ebrahimi Targhi, Gelo Noel Tabia, and Dominique Unruh. Post-Quantum Security of the CBC, CFB, OFB, CTR, and XTS Modes of Operation. In Tsuyoshi Takagi, editor, Post-Quantum Cryptography - 7th International Workshop, PQCrypto 2016, pages 44–63. 2016. Springer, Heidelberg. DOI: 10.1007/978-3-319-29360-8_4
[BBC+21]
Ritam Bhaumik, Xavier Bonnetain, André Chailloux, Gaëtan Leurent, María Naya-Plasencia, André Schrottenloher, and Yannick Seurin. QCB: Efficient Quantum-Secure Authenticated Encryption. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part I, volume 13090 of LNCS, pages 668–698. December 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-92062-3_23
[BBS04]
Dan Boneh, Xavier Boyen, and Hovav Shacham. Short Group Signatures. In Matthew Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 41–55. August 2004. Springer, Heidelberg. DOI: 10.1007/978-3-540-28628-8_3
[BCC+09]
Mira Belenkiy, Jan Camenisch, Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, and Hovav Shacham. Randomizable Proofs and Delegatable Anonymous Credentials. In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 108–125. August 2009. Springer, Heidelberg. DOI: 10.1007/978-3-642-03356-8_7
[BCC+16]
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Essam Ghadafi, and Jens Groth. Foundations of Fully Dynamic Group Signatures. In Mark Manulis, Ahmad-Reza Sadeghi, and Steve Schneider, editors, ACNS 16, volume 9696 of LNCS, pages 117–136. June 2016. Springer, Heidelberg. DOI: 10.1007/978-3-319-39555-5_7
[BCG+18]
Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune K. Jakobsen, and Mary Maller. Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part I, volume 11272 of LNCS, pages 595–626. December 2018. Springer, Heidelberg. DOI: 10.1007/978-3-030-03326-2_20
[BCM+18]
Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh V. Vazirani, and Thomas Vidick. A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. In Mikkel Thorup, editor, 59th FOCS, pages 320–331. October 2018. IEEE Computer Society Press. DOI: 10.1109/FOCS.2018.00038
[BFM88]
Manuel Blum, Paul Feldman, and Silvio Micali. Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). In 20th ACM STOC, pages 103–112. May 1988. ACM Press. DOI: 10.1145/62212.62222
[BG90]
Mihir Bellare and Shafi Goldwasser. New Paradigms for Digital Signatures and Message Authentication Based on Non-Interactive Zero Knowledge Proofs. In Gilles Brassard, editor, CRYPTO'89, volume 435 of LNCS, pages 194–211. August 1990. Springer, Heidelberg. DOI: 10.1007/0-387-34805-0_19
[BKW17]
Dan Boneh, Sam Kim, and David J. Wu. Constrained Keys for Invertible Pseudorandom Functions. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part I, volume 10677 of LNCS, pages 237–263. November 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-70500-2_9
[BP15]
Nir Bitansky and Omer Paneth. ZAPs and Non-Interactive Witness Indistinguishability from Indistinguishability Obfuscation. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015, Part II, volume 9015 of LNCS, pages 401–427. March 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-46497-7_16
[BZ13a]
Dan Boneh and Mark Zhandry. Quantum-Secure Message Authentication Codes. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 592–608. May 2013. Springer, Heidelberg. DOI: 10.1007/978-3-642-38348-9_35
[BZ13b]
Dan Boneh and Mark Zhandry. Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 361–379. August 2013. Springer, Heidelberg. DOI: 10.1007/978-3-642-40084-1_21
[Can01]
Ran Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd FOCS, pages 136–145. October 2001. IEEE Computer Society Press. DOI: 10.1109/SFCS.2001.959888
[CCS09]
Jan Camenisch, Nishanth Chandran, and Victor Shoup. A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks. In Antoine Joux, editor, EUROCRYPT 2009, volume 5479 of LNCS, pages 351–368. April 2009. Springer, Heidelberg. DOI: 10.1007/978-3-642-01001-9_20
[CETU21]
Tore Vincent Carstens, Ehsan Ebrahimi, Gelo Noel Tabia, and Dominique Unruh. Relationships Between Quantum IND-CPA Notions. In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part I, volume 13042 of LNCS, pages 240–272. November 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-90459-3_9
[CEV22]
Céline Chevalier, Ehsan Ebrahimi, and Quoc Huy Vu. On Security Notions for Encryption in a Quantum World. In Takanori Isobe and Santanu Sarkar, editors, Progress in Cryptology - INDOCRYPT 2022 - 23rd International Conference on Cryptology in India, Kolkata, India, December 11-14, 2022, Proceedings, volume 13774 of Lecture Notes in Computer Science, pages 592–613. 2022. Springer. DOI: 10.1007/978-3-031-22912-1_26
[CKL+16]
Jan Camenisch, Stephan Krenn, Anja Lehmann, Gert Læssøe Mikkelsen, Gregory Neven, and Michael Østergaard Pedersen. Formal Treatment of Privacy-Enhancing Credential Systems. In Orr Dunkelman and Liam Keliher, editors, SAC 2015, volume 9566 of LNCS, pages 3–24. August 2016. Springer, Heidelberg. DOI: 10.1007/978-3-319-31301-6_1
[CL01]
Jan Camenisch and Anna Lysyanskaya. An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. In Birgit Pfitzmann, editor, EUROCRYPT 2001, volume 2045 of LNCS, pages 93–118. May 2001. Springer, Heidelberg. DOI: 10.1007/3-540-44987-6_7
[Cv91]
David Chaum and Eugène van Heyst. Group Signatures. In Donald W. Davies, editor, EUROCRYPT'91, volume 547 of LNCS, pages 257–265. April 1991. Springer, Heidelberg. DOI: 10.1007/3-540-46416-6_22
[DDO+01]
Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, and Amit Sahai. Robust Non-interactive Zero Knowledge. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 566–598. August 2001. Springer, Heidelberg. DOI: 10.1007/3-540-44647-8_33
[DFNS14]
Ivan Damgård, Jakob Funder, Jesper Buus Nielsen, and Louis Salvail. Superposition Attacks on Cryptographic Protocols. In Carles Padró, editor, ICITS 13, volume 8317 of LNCS, pages 142–161. 2014. Springer, Heidelberg. DOI: 10.1007/978-3-319-04268-8_9
[DG23]
Quang Dao and Paul Grubbs. Spartan and Bulletproofs are Simulation-Extractable (for Free!). In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part II, volume 14005 of LNCS, pages 531–562. April 2023. Springer, Heidelberg. DOI: 10.1007/978-3-031-30617-4_18
[DP92]
Alfredo De Santis and Giuseppe Persiano. Zero-Knowledge Proofs of Knowledge Without Interaction (Extended Abstract). In 33rd FOCS, pages 427–436. October 1992. IEEE Computer Society Press. DOI: 10.1109/SFCS.1992.267809
[EvW22]
Ehsan Ebrahimi and Jeroen van Wier. Post-quantum Plaintext-Awareness. In Jung Hee Cheon and Thomas Johansson, editors, Post-Quantum Cryptography - 13th International Workshop, PQCrypto 2022, Virtual Event, September 28-30, 2022, Proceedings, volume 13512 of Lecture Notes in Computer Science, pages 260–285. 2022. Springer. DOI: 10.1007/978-3-031-17234-2_13
[FHS19]
Georg Fuchsbauer, Christian Hanser, and Daniel Slamanig. Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials. Journal of Cryptology, 32(2):498–546, April 2019. DOI: 10.1007/s00145-018-9281-4
[FLS90]
Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract). In 31st FOCS, pages 308–317. October 1990. IEEE Computer Society Press. DOI: 10.1109/FSCS.1990.89549
[FS87]
Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, CRYPTO'86, volume 263 of LNCS, pages 186–194. August 1987. Springer, Heidelberg. DOI: 10.1007/3-540-47721-7_12
[GGP10]
Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 465–482. August 2010. Springer, Heidelberg. DOI: 10.1007/978-3-642-14623-7_25
[GGPR13]
Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 626–645. May 2013. Springer, Heidelberg. DOI: 10.1007/978-3-642-38348-9_37
[GMR85]
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). In 17th ACM STOC, pages 291–304. May 1985. ACM Press. DOI: 10.1145/22145.22178
[GO93]
Shafi Goldwasser and Rafail Ostrovsky. Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent (Extended Abstract). In Ernest F. Brickell, editor, CRYPTO'92, volume 740 of LNCS, pages 228–245. August 1993. Springer, Heidelberg. DOI: 10.1007/3-540-48071-4_16
[Gro06]
Jens Groth. Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures. In Xuejia Lai and Kefei Chen, editors, ASIACRYPT 2006, volume 4284 of LNCS, pages 444–459. December 2006. Springer, Heidelberg. DOI: 10.1007/11935230_29
[HU19]
Dennis Hofheinz and Bogdan Ursu. Dual-Mode NIZKs from Obfuscation. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I, volume 11921 of LNCS, pages 311–341. December 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-34578-5_12
[KLLN16]
Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María Naya-Plasencia. Breaking Symmetric Cryptosystems Using Quantum Period Finding. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part II, volume 9815 of LNCS, pages 207–237. August 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-53008-5_8
[KLS18]
Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A Concrete Treatment of Fiat-Shamir Signatures in the Quantum Random-Oracle Model. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part III, volume 10822 of LNCS, pages 552–586. 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-78372-7_18
[KM10]
Hidenori Kuwakado and Masakatu Morii. Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In IEEE International Symposium on Information Theory, ISIT 2010, June 13-18, 2010, Austin, Texas, USA, Proceedings, pages 2682–2685. 2010. IEEE. DOI: 10.1109/ISIT.2010.5513654
[KM12]
Hidenori Kuwakado and Masakatu Morii. Security on the quantum-type Even-Mansour cipher. In Proceedings of the International Symposium on Information Theory and its Applications, ISITA 2012, Honolulu, HI, USA, October 28-31, 2012, pages 312–316. 2012. IEEE.
[KZM+15]
Ahmed Kosba, Zhichao Zhao, Andrew Miller, Yi Qian, Hubert Chan, Charalampos Papamanthou, Rafael Pass, abhi shelat, and Elaine Shi. C$\emptyset$C$\emptyset$: A Framework for Building Composable Zero-Knowledge Proofs. https://eprint.iacr.org/2015/1093. Cryptology ePrint Archive, Paper 2015/1093. 2015.
[LMQW22]
Alex Lombardi, Ethan Mook, Willy Quach, and Daniel Wichs. Post-quantum Insecurity from LWE. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022, Part I, volume 13747 of LNCS, pages 3–32. November 2022. Springer, Heidelberg. DOI: 10.1007/978-3-031-22318-1_1
[LNPT20]
Benoît Libert, Khoa Nguyen, Alain Passelègue, and Radu Titiu. Simulation-Sound Arguments for LWE and Applications to KDM-CCA2 Security. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part I, volume 12491 of LNCS, pages 128–158. December 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-64837-4_5
[Nao90]
Moni Naor. Bit Commitment Using Pseudo-Randomness. In Gilles Brassard, editor, CRYPTO'89, volume 435 of LNCS, pages 128–136. August 1990. Springer, Heidelberg. DOI: 10.1007/0-387-34805-0_13
[NC11]
Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, USA, 10th edition. 2011.
[NS09]
Moni Naor and Gil Segev. Public-Key Cryptosystems Resilient to Key Leakage. In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 18–35. August 2009. Springer, Heidelberg. DOI: 10.1007/978-3-642-03356-8_2
[NY90]
Moni Naor and Moti Yung. Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In 22nd ACM STOC, pages 427–437. May 1990. ACM Press. DOI: 10.1145/100216.100273
[Reg05]
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 84–93. May 2005. ACM Press. DOI: 10.1145/1060590.1060603
[RS19]
Roy Radian and Or Sattath. Semi-Quantum Money. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 132–146, New York, NY, USA. 2019. Association for Computing Machinery. DOI: 10.1145/3318041.3355462
[Sah99a]
Amit Sahai. Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. In 40th FOCS, pages 543–553. October 1999. IEEE Computer Society Press. DOI: 10.1109/SFFCS.1999.814628
[Sah99b]
Amit Sahai. Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. In FOCS 1999, pages 543–553. 1999. IEEE Computer Society. DOI: 10.1109/SFFCS.1999.814628
[Sah01]
Amit Sahai. Simulation-Sound Non-Interactive Zero Knowledge. 2001.
[Sho94]
Peter W. Shor. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In 35th FOCS, pages 124–134. November 1994. IEEE Computer Society Press. DOI: 10.1109/SFCS.1994.365700
[Unr12]
Dominique Unruh. Quantum Proofs of Knowledge. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 135–152. April 2012. Springer, Heidelberg. DOI: 10.1007/978-3-642-29011-4_10
[Unr15]
Dominique Unruh. Non-Interactive Zero-Knowledge Proofs in the Quantum Random Oracle Model. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages 755–784. April 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-46803-6_25
[VV19]
Umesh Vazirani and Thomas Vidick. Fully device independent quantum key distribution. Communications of the ACM, 62(4):133–133, 2019. DOI: 10.1145/3310974
[Wat06]
John Watrous. Zero-knowledge against quantum attacks. In Jon M. Kleinberg, editor, 38th ACM STOC, pages 296–305. May 2006. ACM Press. DOI: 10.1145/1132516.1132560
[WZ82]
William K Wootters and Wojciech H Zurek. A single quantum cannot be cloned. Nature, 299(5886):802–803, 1982.
[Zha12a]
Mark Zhandry. How to Construct Quantum Random Functions. In 53rd FOCS, pages 679–687. October 2012. IEEE Computer Society Press. DOI: 10.1109/FOCS.2012.37
[Zha12b]
Mark Zhandry. Secure Identity-Based Encryption in the Quantum Random Oracle Model. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 758–775. August 2012. Springer, Heidelberg. DOI: 10.1007/978-3-642-32009-5_44
[Zha19]
Mark Zhandry. How to Record Quantum Queries, and Applications to Quantum Indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 239–268. August 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-26951-7_9
PDF
History
Submitted: 2024-10-05
Accepted: 2024-12-03
Published: 2025-01-13
Accepted: 2024-12-03
Published: 2025-01-13
How to cite
Behzad Abdolmaleki, Céline Chevalier, Ehsan Ebrahimi, Giulio Malavolta, and Quoc-Huy Vu, On Quantum Simulation-Soundness. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a66ce0iuc.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.