TY - GEN

T1 - How to delegate computations

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

AU - Kalai, Yael Tauman

AU - Razy, Ran

AU - Rothblumz, Ron D.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We construct a 1-round delegation scheme (i.e., argumentsystem) 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. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval (PIR) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies, a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t(n), we construct a multi-prover interactive proof (MIP) that is sound against no-signaling strategies, where the running time of the provers is poly(t), the number of provers is polylog(t), and the running time of the verifier is n · polylog(t). In particular, this shows that the class of languages that have polynomial-time MIPs that are sound against no-signaling strategies, is exactly EXP. Previously, this class was only known to contain PSPACE. To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al : (ICALP, 2000). This method relies on the existence of a sub-exponentially secure PIR scheme, and was proved secure by Kalai et al : (STOC, 2013) assuming the underlying MIP is secure against no-signaling provers.

AB - We construct a 1-round delegation scheme (i.e., argumentsystem) 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. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval (PIR) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies, a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t(n), we construct a multi-prover interactive proof (MIP) that is sound against no-signaling strategies, where the running time of the provers is poly(t), the number of provers is polylog(t), and the running time of the verifier is n · polylog(t). In particular, this shows that the class of languages that have polynomial-time MIPs that are sound against no-signaling strategies, is exactly EXP. Previously, this class was only known to contain PSPACE. To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al : (ICALP, 2000). This method relies on the existence of a sub-exponentially secure PIR scheme, and was proved secure by Kalai et al : (STOC, 2013) assuming the underlying MIP is secure against no-signaling provers.

KW - Interactive arguments

KW - No-signaling proof-systems

KW - Verifiable delegation

UR - http://www.scopus.com/inward/record.url?scp=84904370060&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904370060&partnerID=8YFLogxK

U2 - 10.1145/2591796.2591809

DO - 10.1145/2591796.2591809

M3 - Conference contribution

AN - SCOPUS:84904370060

SN - 9781450327107

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 485

EP - 494

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

Y2 - 31 May 2014 through 3 June 2014

ER -