A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds

In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation.

In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called ǫ-zero-knowledge. Concretely, we construct the following protocols:

• We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box ǫ-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of ǫ-zero-knowledge property against quantum adversaries requires novel ideas.

• We construct a constant round interactive argument for NP that satisfies computational soundness and black-box ǫ-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions.

At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.

We give two constructions of constant round quantum ǫ-ZK protocols.

• We construct a constant round quantum ǫ-ZK proof for NP assuming the existence of collapsing hash functions [Unr16b, Unr16a], which is considered as a counterpart of collision-resistant hash functions in the quantum setting. Especially, we can instantiate the construction based on the QLWE assumption. Our construction is fully black-box in the sense that both simulation and construction rely on black-box usage of building blocks and a malicious verifier. Interestingly, this construction is just an adapted version of the classical protocol of [GK96] though the proof of quantum ǫ-zero-knowledge property requires novel ideas.

• We construct a constant round quantum ǫ-ZK argument for NP assuming the minimal assumption of the existence of post-quantum OWFs. This construction relies on black-box simulation, but the construction itself is non-black-box.

At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in some sense. We formalize this technique as an extraction lemma, which we believe is of independent interest.

Though we prove a general lemma which we call extraction lemma (Lemma 4.2) and then prove quantum ǫ-ZK of our constructions based on that in the main body, we directly explain the proof of quantum ǫ-ZK without going through such an abstraction in this overview.

Known Classical Technique and Difficulty in Quantum Setting. First, we review a classical constant round ZK proof by Goldreich and Kahan [GK96] (referred to as GK protocol in the following), and explain why it is difficult to prove quantum ZK for this protocol by known techniques. GK protocol is based on a special type of 3-round proof system called Σ-protocol. 5 In a Σ-protocol, a prover sends the first message a, a verifier sends the second message e referred to as a challenge, which is just a public randomness, and the prover sends the third message z. A Σ-protocol satisfies a special type of honest-verifier ZK, which ensures that if a challenge e is fixed, then one can simulate the transcript (a, e, z) without using a witness. Though this may sound like almost the standard ZK property, a difficulty when proving ZK is that a malicious verifier may adaptively choose e depending on a, and thus we cannot fix e at the beginning. To resolve this issue, the idea of GK protocol is to let the verifier commit to a challenge e at the beginning of the protocol. That is, GK protocol roughly proceeds as follows: 6

1. A verifier sends a commitment com to a challenge e of a Σ-protocol.

2. The prover sends the first message a of the Σ-protocol.