Time-optimal interactive proofs for circuit evaluation. (English) Zbl 1316.94093
Canetti, Ran (ed.) et al., Advances in cryptology – CRYPTO 2013. 33rd annual cryptology conference, Santa Barbara, CA, USA, August 18–22, 2013. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-40083-4/pbk). Lecture Notes in Computer Science 8043, 71-89 (2013).
Summary: Several research teams have recently been working toward the development of practical general-purpose protocols for verifiable computation. These protocols enable a computationally weak verifier to offload computations to a powerful but untrusted prover, while providing the verifier with a guarantee that the prover performed the requested computations correctly. Despite substantial progress, existing implementations require further improvements before they become practical for most settings. The main bottleneck is typically the extra effort required by the prover to return an answer with a guarantee of correctness, compared to returning an answer with no guarantee.
We describe a refinement of a powerful interactive proof protocol due to S. Goldwasser et al. [in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 2008. New York, NY: ACM, 113–122 (2008; Zbl 1231.68135)]. G. Cormode, M. Mitzenmacher and J. Thaler [Practical verified computation with streaming interactive proofs. In: ITCS ’12, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, New York, NY: ACM, 90-112 (2012), doi:10.1145/2090236.2090245] show how to implement the prover in this protocol in time \(O(S \log S)\), where \(S\) is the size of an arithmetic circuit computing the function of interest. Our refinements apply to circuits with sufficiently “regular” wiring patterns; for these circuits, we bring the runtime of the prover down to \(O(S)\). That is, our prover can evaluate the circuit with a guarantee of correctness, with only a constant-factor blowup in work compared to evaluating the circuit with no guarantee.
We argue that our refinements capture a large class of circuits, and we complement our theoretical results with experiments on problems such as matrix multiplication and determining the number of distinct elements in a data stream. Experimentally, our refinements yield a 200x speedup for the prover over the implementation of Cormode et al., and our prover is less than \(10\times\) slower than a C++ program that simply evaluates the circuit. Along the way, we describe a special-purpose protocol for matrix multiplication that is of interest in its own right.
Our final contribution is the design of an interactive proof protocol targeted at general data parallel computation. Compared to prior work, this protocol can more efficiently verify complicated computations as long as that computation is applied independently to many different pieces of data.
For the entire collection see [Zbl 1270.94006].
We describe a refinement of a powerful interactive proof protocol due to S. Goldwasser et al. [in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 2008. New York, NY: ACM, 113–122 (2008; Zbl 1231.68135)]. G. Cormode, M. Mitzenmacher and J. Thaler [Practical verified computation with streaming interactive proofs. In: ITCS ’12, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, New York, NY: ACM, 90-112 (2012), doi:10.1145/2090236.2090245] show how to implement the prover in this protocol in time \(O(S \log S)\), where \(S\) is the size of an arithmetic circuit computing the function of interest. Our refinements apply to circuits with sufficiently “regular” wiring patterns; for these circuits, we bring the runtime of the prover down to \(O(S)\). That is, our prover can evaluate the circuit with a guarantee of correctness, with only a constant-factor blowup in work compared to evaluating the circuit with no guarantee.
We argue that our refinements capture a large class of circuits, and we complement our theoretical results with experiments on problems such as matrix multiplication and determining the number of distinct elements in a data stream. Experimentally, our refinements yield a 200x speedup for the prover over the implementation of Cormode et al., and our prover is less than \(10\times\) slower than a C++ program that simply evaluates the circuit. Along the way, we describe a special-purpose protocol for matrix multiplication that is of interest in its own right.
Our final contribution is the design of an interactive proof protocol targeted at general data parallel computation. Compared to prior work, this protocol can more efficiently verify complicated computations as long as that computation is applied independently to many different pieces of data.
For the entire collection see [Zbl 1270.94006].
MSC:
| 94A60 | Cryptography |
