From Secrecy to Soundness: Efficient Verification via Secure Computation by Benny Applebaum, Eyal Kushilevitz, and Yuval Ishai (Presented by Rachel Miller, MIT)
Abstract: We study the problem of verifiable computation (VC) in which
a computationally weak client wishes to delegate the computation of a
function f on an input x to a computationally strong but untrusted
server. We present new general approaches for constructing VC
protocols, as well as solving the related problems of program checking
and self-correcting. The new approaches reduce the task of verifiable
computation to suitable variants of secure multiparty computation
(MPC) protocols. In particular, we show how to efficiently convert the
secrecy property of MPC protocols into soundness of a VC protocol via
the use of a message authentication code (MAC). The new connections
allow us to apply results from the area of MPC towards simplifying,
unifying, and improving over previous results on VC and related
problems. In particular, we obtain the following concrete
applications: (1) The first VC protocols for arithmetic computations
which only make a black-box use of the underlying field or ring; (2) a
non-interactive VC protocol for boolean circuits in the preprocessing
model, conceptually simplifying and improving the online complexity of
a recent protocol of Gennaro et al. (Cryptology ePrint Archive:
Report 2009/547); (3) NC0 self-correctors for complete languages in
the complexity class NC1 and various log-space classes, strengthening
previous AC0 correctors of Goldwasser et al. (STOC 2008).
Joanne Talbot
Last modified: Tue Aug 17 11:00:00 EDT 2010