Takashi Yamakawa, NTT, Japan
We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for NP and give positive and negative results. As a main negative result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for a language outside BQP. As constant-round black-box zero-knowledge arguments for NP exist in the classical setting, our main negative result points out a fundamental difference between post-quantum and classical zero-knowledge protocols assuming that NP is not contained in BQP. On the other hand, as positive results, we construct constant-round post-quantum black-box ϵ-zero-knowledge protocols for NP where the ϵ-zero-knowledge is a mild relaxation of the standard zero-knowledge property. As additional negative results, we show that there is no three-round or public-coin constant-round post-quantum black-box ϵ-zero-knowledge arguments for a language outside BQP. This talk is based on the following works:
A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds. Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa (CRYPTO 2021, QCRYPT 2021, arxiv:2011.02670)
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds. Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa (FOCS 2021, QCRYPT 2021, arXiv:2103.11244)
Recording of the talk