Distributed Zero-Knowledge Proofs Over Networks

Aviv Bick, Gillat Kol, Rotem Oshman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

Zero knowledge proofs are one of the most influential concepts in theoretical computer science. In the seminal definition due to Goldwasser, Micali and Rackoff dating back to the 1980s, a computationally-bounded verifier interacts with a powerful but untrusted prover, with the goal of becoming convinced that the input is in some language. In addition to the usual requirements of completeness and soundness, in a zero knowledge proof, we protect the prover's knowledge: assuming the prover is honest, anything that the verifier can deduce after interacting with the prover, it could have deduced by itself. Zero knowledge proofs have found many applications within theoretical computer science and beyond, e.g., in cryptography, client-cloud computing, blockchains and cryptocurrencies, electronic voting and auctions, and in the financial industry.We define and study the notion of distributed zero knowledge proofs, reconciling the computational notion of zero-knowledge with the communication-based paradigm of distributed graph algorithms. In our setting, a network of verifiers interacts with an untrusted prover to decide some distributed language. As is usually the case in distributed graph algorithms, we assume that the verifiers have local views of the network and each only knows its neighbors. The prover, on the other hand, is assumed to know the entire network graph, as well as any input that the verifier may possess. As in the computational centralized setting, the protocol we design should protect this knowledge. In particular, due to the dual role of the underlying graph in distributed graph algorithms, serving as both the communication topology and the input to the problem, our protocol must protect the graph itself.We construct communication-efficient distributed zero knowledge proofs for two central problems: the 3-coloring problem, one of the poster children of computational zero-knowledge, and for the spanning-tree verification problem, a fundamental building block for designing graph algorithms. We also give a general scheme for converting proof labeling-schemes to distributed zero-knowledge protocols with related parameters. Our protocols combine ideas from computational complexity, distributed computing, and cryptography.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2022
PublisherAssociation for Computing Machinery
Pages2426-2458
Number of pages33
ISBN (Electronic)9781611977073
StatePublished - 2022
Event33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States
Duration: Jan 9 2022Jan 12 2022

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2022-January

Conference

Conference33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Country/TerritoryUnited States
CityAlexander
Period1/9/221/12/22

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Distributed Zero-Knowledge Proofs Over Networks'. Together they form a unique fingerprint.

Cite this