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

Understand

A major difficulty in quantum rewinding is the fact that measurement is destructive: extracting information from a quantum state irreversibly changes it.

• This is especially problematic in the context of zero-knowledge simulation, where preserving the adversary's state is essential.
• In this work, we develop new techniques for quantum rewinding in the context of extraction and zero-knowledge simulation: (1) We show how to extract information from a quantum adversary by rewinding it without disturbing its internal state.
• We use this technique to prove that important interactive protocols, such as the Goldreich-Micali-Wigderson protocol for graph non-isomorphism and the Feige-Shamir protocol for NP, are zero-knowledge against quantum adversaries.