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 $F$ on input $x$ to a polynomial time worker, who computes the output $y=F(x)$ and proves to the delegator the correctness of the output. Let $T$ be the complexity of computing $F$ on inputs of length $n=\abs x $ and let $k$ 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 $x$. The total computational complexity of the delegator during off-line and on-line stages is $ \poly(k, n, \log T)$. 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 $\poly(k,n, T)$. Thus, they achieve delegator complexity $\poly(k, n, \log T)$ 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 $F$ rather than being restricted to $\NC$ computable $F$. Our second scheme requires no off-line stage and has a two-message ``on-line'' stage with complexity of $\poly(k, n, \log T)$. 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 $\NC$ computations.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Designated Verifier CS ProofsDelegationKnowledge of Exponent Assumption
- Contact author(s)
-
huijia @ cs cornell edu
aviadrub @ mail tau ac il
shafi @ theory csail mit edu - History
- 2011-08-21: received
- Short URL
- https://ia.cr/2011/456
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2011/456, author = {Shafi Goldwasser and Huijia Lin and Aviad Rubinstein}, title = {Delegation of Computation without Rejection Problem from Designated Verifier {CS}-Proofs}, howpublished = {Cryptology {ePrint} Archive, Paper 2011/456}, year = {2011}, url = {https://eprint.iacr.org/2011/456} }