Cryptology ePrint Archive: Report 2022/063
Non-Interactive Zero-Knowledge Proofs to Multiple Verifiers
Kang Yang and Xiao Wang
Abstract: In this paper, we study zero-knowledge (ZK) proofs for circuit satisfiability that can prove to $n$ verifiers at a time efficiently. The proofs are secure against the collusion of a prover and a subset of $t$ verifiers. We refer to such ZK proofs as multi-verifier zero-knowledge (MVZK) proofs and focus on the case that a majority of verifiers are honest (i.e., $t<n/2$). We construct efficient MVZK protocols in the random oracle model where the prover sends one message to each verifier, while the verifiers only exchange one round of messages. When the threshold of corrupted verifiers $t<n/2$, the prover sends $1/2+o(1)$ field elements per multiplication gate to every verifier; when $t<n(1/2-\epsilon)$ for any $0<\epsilon<1/2$, we can further reduce the communication to $O(1/n)$ field elements per multiplication gate per verifier. Our MVZK protocols demonstrate particularly high scalability: the proofs are streamable and only require a memory proportional to what is needed to evaluate the circuit in the clear.
Category / Keywords: cryptographic protocols / zero-knowledge proofs, multiple verifiers
Date: received 18 Jan 2022, last revised 17 Feb 2022
Contact author: yangk at sklc org, wangxiao at cs northwestern edu
Available format(s): PDF | BibTeX Citation
Version: 20220217:114430 (All versions of this report)
Short URL: ia.cr/2022/063
[ Cryptology ePrint archive ]