The power of distributed verifiers in interactive proofs

by Moni Naor, Merav Parter and Eylon Yogev

Oded's comments

The most basic paradigm of proof systems presumes that the prover is more powerful than the verifier. In this work, this paradigm is interpreted by viewing a centralized system as more powerful than a distributed one.

The verifier is modeled as a network, and the underlying graph of this network plays two roles: (1) defining the communication channels between processors, and (2) being part of the input. In addition, each processor may obtain a local input, and the processors collectively verify claims (made by an external prover) regarding the graph and the collection of local inputs.

The main result is a transformation of verifier's programs for the standard interactive proof setting to programs for the distributed verifier of the current model. When reading the specific results, one should bear in mind that $n$ denotes the number of processors, and that the input length may be $n^2$ (since the input may contain a general $n$-vertex graph). Hence, some of the results are obatined by decomposing the original verifier into a sublinear (in $n^2$) module and a specific computation, applying the transformation to the former module and implementing the second module directly.

The original 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.

This interactive model was introduced by Kol, Oshman and Saxena (PODC 2018) as a generalization of non-interactive distributed proofs. They demonstrated the power of interaction in this setting by constructing protocols for problems as Graph Symmetry and Graph Non-Isomorphism -- both of which require proofs of (n^2)-bits without interaction.

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. We show the following:

Our compilers capture many natural problems and demonstrate the difficulty in showing lower bounds in these regimes.

See ECCC TR18-213.

Back to list of Oded's choices.