CryptoDB
Distributed-Prover Interactive Proofs
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2023 |
| Abstract: | Interactive proof systems enable a verifier with limited resources to decide an intractable language (or compute a hard function) by communicating with a powerful but untrusted prover. Such systems guarantee soundness: the prover can only convince the verifier of true statements. This is a central notion in computer science with far-reaching implications. One key drawback of the classical model is that the data on which the prover operates must be held by a single machine. In this work, we initiate the study of distributed-prover interactive proofs (dpIPs): an untrusted cluster of machines, acting as a distributed prover, interacts with a single verifier. The machines in the cluster jointly store and operate on a massive data-set that no single machine can store. The goal is for the machines in the cluster to convince the verifier of the validity of some statement about its data-set. We formalize the communication and space constraints via the massively parallel computation (MPC) model, a widely accepted analytical framework capturing the computational power of massive data-centers. Our main result is a compiler that generically augments any verification algorithm in the MPC model with a soundness guarantee. Concretely, for any language $L$ for which there is an MPC algorithm verifying whether $x{\in} L$, we design a new MPC protocol capable of convincing a verifier of the validity of $x\in L$ and where if $x\not\in L$, the verifier will reject almost surely reject, no matter what. The new protocol requires only slightly more rounds, i.e., a $\mathsf{poly}(\log N)$ blowup, and a slightly bigger memory per machine, i.e., $\mathsf{poly}(\lambda)$ blowup, where $N$ is the total size of the dataset and $\lambda$ is a security parameter independent of $N$. En route, we introduce distributed-prover interactive oracle proofs (dpIOPs), a natural adaptation of the (by now classical) IOP model to the distributed prover setting. We design a dpIOP for algorithms in the MPC model and then tranlate them to ``plain model'' dpIPs via an adaptation of existing polynomial commitment schemes into the distributed prover setting. |
BibTeX
@inproceedings{tcc-2023-33653,
title={Distributed-Prover Interactive Proofs},
publisher={Springer-Verlag},
author={Sourav Das and Rex Fernando and Ilan Komargodski and Elaine Shi and Pratik Soni},
year=2023
}