Time+Place: Thursday 03/04/2014 14:30 Room 337-8 Taub Bld.
Title: Verifying the correctness of remote executions: from theoretical possibility to near practicality
Speaker: Michael Walfish - Colloquium Lecture http://www.cs.nyu.edu/~mwalfish/
Affiliation: Computer Science Dept., NYU
Host: Yuval Ishai


How can a machine specify a computation to another one and then, without
executing the computation, check that the remote machine carried it out
correctly? And how can this be done without assumptions about the
performer (replication, etc.) or restrictions on the computation? This
is a classic problem in systems security, and it is particularly
relevant in the context of cloud computing. For decades, it has been
known that this problem can be solved in theory, using probabilistically
checkable proofs (PCPs) coupled with cryptographic tools. The rub was
practicality: if implemented naively, the theory would be astronomically
more expensive than simply executing the computation locally.

Over the last several years, a number of projects have brought this
theory to near practicality in the context of implemented systems.  In
this emerging area of _proof-based verifiable computation_, the pace of
progress has been rapid, and there have been many encouraging
developments. I will discuss this general area and my group's efforts.
We have refined an elegant protocol of Ishai, Kushilevitz, and Ostrovsky
(CCC '07); broadened the computational model from Boolean circuits to
something general-purpose; developed a compiler that transforms from
programs to executables that implement the protocol entities; fully
implemented the system; accelerated it with GPUs; and extended the
machinery to handle real applications of the cloud (MapReduce, etc.).

I will also cover the remaining obstacles to true practicality in this
research area. My hope is to communicate cautious optimism.


Michael Walfish is an associate professor in the CS department at New
York University (NYU), which he joined at the beginning of this year.
Prior to that, he was an assistant professor at The University of Texas
at Austin. His research interests are in systems, security, and
networking.  His honors include an Air Force Young Investigator Award,
an NSF CAREER Award, a Sloan Research Fellowship, a Teaching Excellence
Award from the UT College of Natural Sciences, the Intel Early Career
Faculty Honor Program, and the UT Society for Teaching Excellence. He
received his B.A. from Harvard and his Ph.D. from MIT, both in Computer

Desserts will be served from 14:15
Lecture starts at 14:30