Verifying Computations with Streaming Interactive Proofs

Understand

When computation is outsourced, the data owner would like to be assured that the desired computation has been performed correctly by the service provider.

• In theory, proof systems can give the necessary assurance, but prior work is not sufficiently scalable or practical.
• 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.