Computer Science Colloquium
Thursday, March 6, 4:15-5:30pm, room 9204
Rosario Gennaro (CCNY)
"A Survey of Verifiable Delegation of Computations"
In this talk I will give an overview of past and recent research on the area of Verifiable Delegation of Computation. The goal is to enable a computationally weak client to "outsource" the computation of a function F on various inputs x_1,...,x_k to one or more powerful servers. The server must return the result of the function evaluation, e.g., y_i=F(x_i), as well as a proof that the computation of F was carried out correctly on the given value x_i. A crucial requirement is that the verification of the proof should require substantially less computational effort than computing F(x_i) from scratch.
For the "general purpose" case (protocols that work for any function F) I will discuss the different ways this problem has been approached theoretically, particularly the line of research that links Interactive Proofs, to Probabilistic Checkable Proofs, to Succinct Non-Interactive Arguments. I will also survey recent exciting experimental results that show how these techniques are on the verge of becoming practical.