Post-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably

Alex Lombardi, Fermi Ma, Nicholas Spooner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

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 (a) precisely captures all of our zero-knowledge simulators, (b) cannot break any polynomial hardness assumptions, (c) implies strict polynomial-time ?-simulation and (d) 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.

Original languageEnglish (US)
Title of host publicationProceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
PublisherIEEE Computer Society
Pages851-859
Number of pages9
ISBN (Electronic)9781665455190
DOIs
StatePublished - 2022
Externally publishedYes
Event63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States
Duration: Oct 31 2022Nov 3 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-October
ISSN (Print)0272-5428

Conference

Conference63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
Country/TerritoryUnited States
CityDenver
Period10/31/2211/3/22

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • post quantum cryptography
  • zero knowledge proofs

Fingerprint

Dive into the research topics of 'Post-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably'. Together they form a unique fingerprint.

Cite this