Paper 2011/456

Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs

Shafi Goldwasser, Huijia Lin, and Aviad Rubinstein

Abstract

We present a designated verifier CS proof system for polynomial time computations. The proof system can only be verified by a designated verifier: one who has published a public-key for which it knows a matching secret key unknown to the prover. Whereas Micali's CS proofs require the existence of random oracles, we can base soundness on computational assumptions: the existence of leveled fully homomorphic encryption (FHE) schemes, the DDH assumption and a new knowledge of exponent assumption. Using our designated verifier CS proof system, we construct two schemes for delegating (polynomial-time) computation. In such schemes, a delegator outsources the computation of a function $$ on input $$ to a polynomial time worker, who computes the output $$ and proves to the delegator the correctness of the output. Let $$ be the complexity of computing $$ on inputs of length $$ and let $$ be a security parameter. Our first scheme calls for an one-time off-line stage where the delegator sends a message to the worker, and a non-interactive on-line stage where the worker sends the output together with a certificate of correctness to the prover per input $$. The total computational complexity of the delegator during off-line and on-line stages is $$. Compared with previous constructions by Gennaro-Gentry-Parno and Chung-Kalai-Vadhan~\cite{GGP10, CKV10} based on FHE, their on-line stage consists of two messages and their off-line stage has (delegator's) complexity of $$. Thus, they achieve delegator complexity $$ only in an amortized sense. Compared with the construction of \cite{GKR08} based on poly-log PIR, our first construction can handle any polynomial-time computable $$ rather than being restricted to $$ computable $$. Our second scheme requires no off-line stage and has a two-message ``on-line'' stage with complexity of $$. Most importantly, it achieves {\em robust soundness} that guarantees that it is infeasible for a cheating worker to convince the delegator of an invalid output even if the worker learns whether the delegator accepts or rejects previous outputs and proofs. Previously the only two-round protocol that achieves robust soundness under a computational assumption appeared in \cite{GKR08} and is restricted to only $$ computations.