

Bristol Algorithms Days 2010 Feasibility Workshop
15  16 February 2010

SIPping from the firehose: Streaming Interactive Proofs for verifying
computations.
Graham Cormode
When handling large quantities of data, it is desirable to outsource
the computational effort to a third party: this captures current
efforts in cloud computing, but also scenarios within trusted
computing systems and interorganizational data sharing. When the
third party is not fully trusted, it is desirable to give assurance
that the computation has been perfomed correctly. This talk presents
some recent results in designing new protocols for verifying
computations which are streaming in nature: the verifier (data owner)
needs only a single pass over the input, storing a sublinear amount of
information, and follows a simple protocol with a prover (serice
provider) that takes a small number of rounds. A dishonest prover
fools the verifier with only polynomially small probabiliy, while an
honest prover's answer is always accepted. Within this model, we show
protocols for a variety of problems that select items from the input
(e.g. median, heavy hitters), or compute certain aggregates or
structures (e.g. frequency moments, number of triangles in a graph).
These problems require linear space to compute (exactly) in the
traditional streaming model, showing that outsourcing can
exponentially reduce the effort needed by the verifier to obtain
correct answers.
Back
 