Dishonest Majority Multi-Verifier Zero-Knowledge Proofs for Any Constant Fraction of Corrupted Verifiers

Daniel Escudero; Antigoni Polychroniadou; Yifan Song; Chenkai Weng

Paper 2024/997

Dishonest Majority Multi-Verifier Zero-Knowledge Proofs for Any Constant Fraction of Corrupted Verifiers

Daniel Escudero

, J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE, NY, USA

Antigoni Polychroniadou, J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE, NY, USA

Yifan Song, Tsinghua University, Beijing, China, Shanghai Qi Zhi Institute, Shanghai, China

Chenkai Weng, Arizona State University, AZ, USA

Abstract

In this work we study the efficiency of Zero-Knowledge (ZK) arguments of knowledge, particularly exploring Multi-Verifier ZK (MVZK) protocols as a midway point between Non-Interactive ZK and Designated-Verifier ZK, offering versatile applications across various domains. We introduce a new MVZK protocol designed for the preprocessing model, allowing any constant fraction of verifiers to be corrupted, potentially colluding with the prover. Our contributions include the first MVZK over rings. Unlike recent prior works on fields in the dishonest majority case, our protocol demonstrates communication complexity independent of the number of verifiers, contrasting the linear complexity of previous approaches. This key advancement ensures improved scalability and efficiency. We provide an end-to-end implementation of our protocol. The benchmark shows that it achieves a throughput of 1.47 million gates per second for 64 verifiers with $50\%$ corruption, and 0.88 million gates per second with $75\%$ corruption.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. CCS 2024
Keywords: Zero-Knowledge Proofs Multiverifier
Contact author(s): daniel escudero @ protonmail com
antigonipoly @ gmail com
yfsong @ mail tsinghua edu cn
car1ckweng @ gmail com
History: 2024-06-22: last of 2 revisions; 2024-06-20: received; See all versions
Short URL: https://ia.cr/2024/997
License: CC BY

BibTeX

@misc{cryptoeprint:2024/997,
      author = {Daniel Escudero and Antigoni Polychroniadou and Yifan Song and Chenkai Weng},
      title = {Dishonest Majority Multi-Verifier Zero-Knowledge Proofs for Any Constant Fraction of Corrupted Verifiers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/997},
      year = {2024},
      url = {https://eprint.iacr.org/2024/997}
}