Our first construction eliminates the large public key from the Gennaro et al. scheme. The delegator still invests $poly(T)$ time in the offline stage, but does not need to communicate or publish anything. Our second construction reduces the work of the delegator in the offline stage to $poly(log T)$ at the price of a 4-message (offline) interaction with a $poly(T)$-time worker (which need not be the same as the workers used in the online stage). Finally, we describe a "pipelined" implementation of the second construction that avoids the need to re-run the offline construction after errors are detected (assuming errors are not too frequent).
Category / Keywords: cryptographic protocols / verifiable computation, outsourcing computation, worst-case/average-case reductions, computationally sound proofs, universal argument systems Date: received 28 Apr 2010, last revised 28 Apr 2010 Contact author: kmchung at fas harvard edu Available format(s): PDF | BibTeX Citation Version: 20100502:164820 (All versions of this report) Short URL: ia.cr/2010/241 Discussion forum: Show discussion | Start new discussion