Paper 2020/1384

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.

Note: Fixed a minor technical issue (see Footnote 17 in page 21) and improved the proof of Claim 4.5. (10/30/2023)

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2021
quantum cryptographyzero knowledge
Contact author(s)
nc67 @ rice edu
kmchung @ iis sinica edu tw
takashi yamakawa @ ntt com
2023-10-30: last of 2 revisions
2020-11-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nai-Hui Chia and Kai-Min Chung and Takashi Yamakawa},
      title = {A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1384},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.