When computation is outsourced, the data owner would like to be reassured that the desired computation has been performed correctly by the service provider. In theory, methods based on proof systems can give the data owner the necessary assurance, but previous work does not give a sufficiently scalable and practical solution, requiring a lot of time, space or computational power for both parties. In this paper, we develop new proof protocols for verifying computations which are streaming in nature: the verifier (data owner) needs only logarithmic space and a single pass over the input, and after observing the input follows a simple protocol with a prover (service provider) that takes logarithmic communication spread over a logarithmic number of rounds. These ensure that the computation is performed correctly: that the service provider has not made any errors or missed out some data. The guarantee is very strong: even if the service provider deliberately tries to cheat, there is only vanishingly small probability of doing so undetected, while a correct computation is always accepted. We first observe that some existing theoretical results can be modified to work with streaming verifiers, which shows that there exist efficient protocols for problems in the complexity classes NP and NC. Our main results seek to bridge the gap between theory and practice by developing usable protocols for a variety of problems of central importance in streaming and database processing. All of our protocols achieve statistical soundness and most require only logarithmic communication between prover and verifier. We also experimentally demonstrate their practicality and scalability. All these problems require linear space in the traditional streaming model, showing that adding a prover can exponentially reduce the effort needed by the verifier.
[ bib | Alternate Version | .pdf ] Back
This file was generated by bibtex2html 1.92.