Paper Info
Title
Post-quantum Resettably-Sound Zero Knowledge
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-GoldwasserLindell, 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 blackbox 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 very different 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 postquantum resettably-sound zero knowledge protocol for NP. We rely on non-black-box simulation techniques, thus overcoming the blackbox 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.
Year
DOI
Venue
2021
10.1007/978-3-030-90459-3_3
THEORY OF CRYPTOGRAPHY, TCC 2021, PT I
DocType
Volume
ISSN
Conference
13042
0302-9743
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Nir Bitansky183331.00
Michael Kellner200.34
Omri Shmueli311.71