Computer Science Colloquium, 03/06/2014

MAR 06, 2014 | 4:15 PM

Details

WHERE:

The Graduate Center
365 Fifth Avenue

ROOM:

9204

WHEN:

March 06, 2014: 4:15 PM

ADMISSION:

Free

Description

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.