Paper 2021/1543

Post-Quantum Zero Knowledge, Revisited (or: How to do Quantum Rewinding Undetectably)

Alex Lombardi, Massachusetts Institute of Technology
Fermi Ma, Simons Institute, University of California, Berkeley
Nicholas Spooner, University of Warwick

When do classical zero-knowledge protocols remain secure against quantum attacks? In this work, we develop the techniques, tools, and abstractions necessary to answer this question for foundational protocols: 1) We prove that the Goldreich-Micali-Wigderson protocol for graph non-isomorphism and the Feige-Shamir protocol for NP remain zero-knowledge against quantum adversaries. At the heart of our proof is a new quantum rewinding technique that enables extracting information from multiple invocations of a quantum adversary without disturbing its state. 2) We prove that the Goldreich-Kahan protocol for NP is post-quantum zero knowledge using a simulator that can be seen as a natural quantum extension of the classical simulator. Our results achieve negligible simulation error, appearing to contradict a recent impossibility result due to Chia-Chung-Liu-Yamakawa (FOCS 2021). This brings us to our final contribution: 3) We introduce coherent-runtime expected quantum polynomial time, a simulation notion that (1) precisely captures all of our zero-knowledge simulators, (2) cannot break any polynomial hardness assumptions, (3) implies strict polynomial-time epsilon-simulation and (4) is not subject to the CCLY impossibility. In light of our positive results and the CCLY negative results, we propose coherent-runtime simulation to be the appropriate quantum analogue of classical expected polynomial-time simulation.

Available format(s)
Publication info
Published elsewhere. FOCS 2022
quantum rewinding zero knowledge proofs of knowledge
Contact author(s)
alexlombardi @ alum mit edu
fermima @ alum mit edu
nicholas spooner @ warwick ac uk
2022-09-23: revised
2021-11-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alex Lombardi and Fermi Ma and Nicholas Spooner},
      title = {Post-Quantum Zero Knowledge, Revisited (or: How to do Quantum Rewinding Undetectably)},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1543},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.