Paper 2021/349

Post-quantum Resettably-Sound Zero Knowledge

Nir Bitansky, Michael Kellner, and Omri Shmueli

Abstract

We study post-quantum zero-knowledge (classical) protocols that are sound against quantum resetting attacks. Our model is inspired by the classical model of resetting provers (Barak-Goldreich-Goldwasser-Lindell, FOCS `01), providing a malicious efficient prover with oracle access to the verifier's next-message-function, fixed to some initial random tape; thereby allowing it to effectively reset (or equivalently, rewind) the verifier. In our model, the prover has quantum access to the verifier's function, and in particular can query it in superposition. The motivation behind quantum resettable soundness is twofold: First, ensuring a strong security guarantee in scenarios where quantum resetting may be possible (e.g., smart cards, or virtual machines). Second, drawing intuition from the classical setting, we hope to improve our understanding of basic questions regarding post-quantum zero knowledge. We prove the following results: Black-Box Barriers: Quantum resetting exactly captures the power of black-box zero knowledge quantum simulators. Accordingly, resettable soundness cannot be achieved in conjunction with black-box zero knowledge, except for languages in $\BQP$. Leveraging this, we prove that constant-round public-coin, or three message, protocols cannot be black-box post-quantum zero-knowledge. For this, we show how to transform such protocols into quantumly resettably sound ones. The transformations are similar to classical ones, but their analysis is significantly more challenging due to the essential difference between classical and quantum resetting. A Resettably-Sound Non-Black-Box Zero-Knowledge Protocol: Under the (quantum) Learning with Errors assumption and quantum fully-homomorphic encryption, we construct a post-quantum resettably-sound zero knowledge protocol for $\NP$. We rely on non-black-box simulation techniques, thus overcoming the black-box barrier for such protocols. From Resettable Soundness to The Impossibility of Quantum Obfuscation: Assuming one-way functions, we prove that any quantumly-resettably-sound zero-knowledge protocol for $\NP$ implies the impossibility of quantum obfuscation. Combined with the above result, this gives an alternative proof to several recent results on quantum unobfuscatability.