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.
We suggest 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.
One of the main tools we construct is a compiler that takes any (centralized) computation performed in time O(n) on a RAM and translates it into a three-round distributed interactive protocol with O(log n) proof size. The transformation is based on memory checking. We extend this compiler to languages that can be computed in small space or by a small depth circuit as well.
We demonstrate the power of our compiler for specific problems such as Graph Non-Isomorphism, Clique and Leader Election.
Joint work with Merav Parter and Moni Naor