Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Delegation:
TR13-183 | 22nd December 2013
Yael Tauman Kalai, Ran Raz, Ron Rothblum

How to Delegate Computations: The Power of No-Signaling Proofs

Revisions: 1

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n*polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. ... more >>>

TR16-077 | 12th May 2016
Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

Non-Interactive RAM and Batch NP Delegation from any PIR

Revisions: 1

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of ... more >>>

TR18-161 | 13th September 2018
Justin Holmgren, Ron Rothblum

Delegating Computations with (almost) Minimal Time and Space Overhead

The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as ... more >>>

ISSN 1433-8092 | Imprint