Computer Science – Data Structures and Algorithms
Scientific paper
2011-05-10
Computer Science
Data Structures and Algorithms
39 pages, 12 figures, 2 tables. Accepted to ITCS 2012
Scientific paper
When delegating computation to a service provider, as in cloud computing, we seek some reassurance that the output is correct and complete. Yet recomputing the output as a check is inefficient and expensive, and it may not even be feasible to store all the data locally. We are therefore interested in proof systems which allow a service provider to prove the correctness of its output to a streaming (sublinear space) user, who cannot store the full input or perform the full computation herself. Our approach is two-fold. First, we describe a carefully chosen instantiation of one of the most efficient general-purpose constructions for arbitrary computations (streaming or otherwise), due to Goldwasser, Kalai, and Rothblum. This requires several new insights to make the methodology more practical. Our main contribution is in achieving a prover who runs in time O(S(n) log S(n)), where S(n) is the size of an arithmetic circuit computing the function of interest. Our experimental results demonstrate that a practical general-purpose protocol for verifiable computation may be significantly closer to reality than previously realized. Second, we describe techniques that achieve genuine scalability for protocols fine-tuned for specific important problems in streaming and database processing. Focusing in particular on non-interactive protocols for problems ranging from matrix-vector multiplication to bipartite perfect matching, we build on prior work to achieve a prover who runs in nearly linear-time, while obtaining optimal tradeoffs between communication cost and the user's working memory. Existing techniques required (substantially) superlinear time for the prover. We argue that even if general-purpose methods improve, fine-tuned protocols will remain valuable in real-world settings for key problems, and hence special attention to specific problems is warranted.
Cormode Graham
Mitzenmacher Michael
Thaler Justin
No associations
LandOfFree
Practical Verified Computation with Streaming Interactive Proofs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Practical Verified Computation with Streaming Interactive Proofs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Practical Verified Computation with Streaming Interactive Proofs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-280637