Interactive distributed proofs

Gillat Kol, Rotem Oshman, Raghuvansh R. Saxena

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

8 Scopus citations

Abstract

Interactive proof systems allow a resource-bounded verifier to decide an intractable language (or compute a hard function) by communicating with a powerful but untrusted prover. Such systems guarantee that the prover can only convince the verifier of true statements. In the context of centralized computation, a celebrated result shows that interactive proofs are extremely powerful, allowing polynomial-time verifiers to decide any language in PSPACE. In this work we initiate the study of interactive distributed proofs: a network of nodes interacts with a single untrusted prover, who sees the entire network graph, to decide whether the graph satisfies some property. We focus on the communication cost of the protocol - the number of bits the nodes must exchange with the prover and each other. Our model can also be viewed as a generalization of the various models of “distributed NP” (proof labeling schemes, etc.) which received significant attention recently: while these models only allow the prover to present each network node with a string of advice, our model allows for back-and-forth interaction. We prove both upper and lower bounds for the new model. We show that for some problems, interaction can exponentially decrease the communication cost compared to a non-interactive prover, but on the other hand, some problems retain non-trivial cost even with interaction.

Original languageEnglish (US)
Title of host publicationPODC 2018 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages255-264
Number of pages10
ISBN (Print)9781450357951
DOIs
StatePublished - Jul 23 2018
Event37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2018 - Egham, United Kingdom
Duration: Jul 23 2018Jul 27 2018

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2018
CountryUnited Kingdom
CityEgham
Period7/23/187/27/18

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Interactive distributed proofs'. Together they form a unique fingerprint.

  • Cite this

    Kol, G., Oshman, R., & Saxena, R. R. (2018). Interactive distributed proofs. In PODC 2018 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (pp. 255-264). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). Association for Computing Machinery. https://doi.org/10.1145/3212734.3212772