Paper 2022/063

Non-Interactive Zero-Knowledge Proofs to Multiple Verifiers

Kang Yang, State Key Laboratory of Cryptology
Xiao Wang, Northwestern University
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 some constant $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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Keywords
zero-knowledge proofs
Contact author(s)
yangk @ sklc org
wangxiao @ cs northwestern edu
History
2022-09-18: last of 2 revisions
2022-01-18: received
See all versions
Short URL
https://ia.cr/2022/063
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/063,
      author = {Kang Yang and Xiao Wang},
      title = {Non-Interactive Zero-Knowledge Proofs to Multiple Verifiers},
      howpublished = {Cryptology ePrint Archive, Paper 2022/063},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/063}},
      url = {https://eprint.iacr.org/2022/063}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.