This paper initiates the study of the practical efficiency of multiprover interactive proofs (MIPs). We present a new MIP for delegating computation that extends insights from a powerful IP protocol (Goldwasser et al., STOC, 2008). Without reductions or amplification, our protocol uses only two provers (departing from prior work on MIPs), and achieves both the efficiency of interactive proof-based protocols and the generality of argument system-based protocols. Also, this result, together with recently developed machinery, creates a potential avenue toward concretely efficient arguments without setup costs.
We describe Clover, a built system for verifiable computation, based on our protocol. Although Clover does not implement the full theory (it has setup costs), it applies to problems that existing IPs cannot efficiently handle, and achieves performance comparable to, or better than, the best argument systems.
Category / Keywords: foundations / interactive proofs, verifiable computation, circuit evaluation Date: received 16 Oct 2014, last revised 22 Oct 2014 Contact author: jthaler at fas harvard edu Available format(s): PDF | BibTeX Citation Note: Author order corrected to be alphabetical. Version: 20141022:192726 (All versions of this report) Short URL: ia.cr/2014/846 Discussion forum: Show discussion | Start new discussion