Abstract of PhD Thesis (Weizmann Inst., 2015)
Title: Verifiable Outsourcing of Computation
We study the question of designing protocols for allowing a
computationally weak client to outsource its computations to a
powerful but untrusted server. Since the client does not trust
the server, the latter must convince the client that the result
of the computation is correct. The two crucial points are
that (1) verifying the correctness must be much easier than
directly performing the computation, and (2) the overhead on the
server's side must be minimal. Our main results are:
(Almost) Linear-Time Verification: We show a general-purpose
single-round protocol that allows the client to outsource the
computation of any function computable in (arbitrarily large)
polynomial-time such that the correctness of the computation
can be verified in (almost) linear-time, with only a
polynomial overhead for the server. The security of our
protocol relies on the security of a standard cryptographic primitive.
Sublinear-Time Verification: In some settings even linear-time
verification may not be feasible. We initiate the study of
non-interactive proofs of proximity. These allow the client to verify
a given statement in sub-linear time, using a short (sublinear length)
explicitly given certificate (i.e., proof) from the server.
Since the client cannot even read its entire input,
following the property testing literature, we only guarantee
an approximate answer. This notion can be viewed as the NP
(or more accurately MA) analogue of property testing.
Submitted to the Feinberg Graduate School
of the Weizmann Institute of Science, March 2015.
thesis (in PDF file).
Back to Oded Goldreich's homepage.