Ron Rothblum

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:

  1. (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.
  2. 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.

Available: the thesis (in PDF file).


Back to Oded Goldreich's homepage.