The TAU Programming Languages and Systems Seminar - The Power of Distributed Verifiers in Interactive Proofs

ABSTRACT:

We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of n nodes and a graph G that defines their communication pattern. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G belongs to some language in a small number of rounds, and with small communication bound, i.e., the proof size.

In this work, we provide a new general framework for distributed interactive proofs that allows one to translate standard interactive protocols (i.e., with a centralized verifier) to ones where the verifier is distributed with a proof size that depends on the computational complexity of the verification algorithm run by the centralized verifier.

As our main result, we show that every (centralized) computation performed in time O(n) on a RAM can be translated into a three-round distributed interactive protocol with O(log n) proof size. This implies that many graph problems for sparse graphs have succinct proofs (e.g., testing planarity).

We extend this compiler to hand languages that can be computed in small space or by a small depth circuit as well. We further demonstrate the power of our compiler for specific problems such as Graph Non-Isomorphism, Clique and Leader Election (for the latter two problems we get O(1) proof size).

Joint work with Merav Parter and Moni Naor.