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

Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa

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 $\epsilon$-zero-knowledge. Concretely, we
construct the following protocols:
- We construct a constant round interactive proof for NP that satisfies
statistical soundness and black-box $\epsilon$-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 $\epsilon$-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 $\epsilon$-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.