Non-Interactive Verifiable Computing

We introduce and formalize the notion of Verifiable Computation, which enables a computationally weak client to “outsource” the computation of a function F on various dynamically-chosen inputs to one or more workers. The primary constraint is that the verification of the results should require substantially less effort than computing F from scratch.

We present a protocol that allows the worker to return a computationally-sound, non-interactive proof that can be verified in O(m * poly(lambda)) time, where m is the bit-length of the output of F, and lambda is a security parameter. The protocol requires a one-time pre-processing stage by the client which takes O(|C| * poly(lambda)) time, where C is the smallest known Boolean circuit computing F.

Finally, we present new constructions that promise substantially better performance in practice, though current instantiations do not achieve the full set of desirable properties for verifiable computing.

Speaker Details

Bryan Parno is a researcher in Microsoft Research’s Security and Privacy Research Group. He received his PhD and Master’s degrees at Carnegie Mellon University, where he was advised by Adrian Perrig, and a Bachelor’s degree from Harvard University. His current work focuses on the foundations of trust on modern computers. His research interests include computer security, systems, networks, and applied cryptography. In his spare time, he enjoys photography and volunteering as an Emergency Medical Technician.

Date:
Speakers:
Bryan Parno
Affiliation:
MSR
    • Portrait of Bryan Parno

      Bryan Parno

    • Portrait of Jeff Running

      Jeff Running