TY - GEN

T1 - Delegation for bounded space

AU - Kalai, Yael Tauman

AU - Raz, Ran

AU - Rothblum, Ron D.

PY - 2013

Y1 - 2013

N2 - We construct a 1-round delegation scheme for every language computable in time t = t(n) and space s = s(n), where the running time of the prover is poly(t) and the running time of the verifier is Õ (n + poly(s)) (where Õ hides polylog(t) factors). 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 (cheat- ing) 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) and space s = s(n), we construct MIPs that are sound against no-signaling strategies, where the running time of the provers is poly(t), the number of provers is Õ (s), and the running time of the verifier is Õ (s + n). We then show how to use the method suggested by Aiello et al : (ICALP, 2000) to convert our MIP into a 1-round delegation scheme, by using a computational private information retrieval (PIR) scheme. Thus, assuming the existence of a sub-exponentially secure PIR scheme, we get our 1-round delegation scheme.

AB - We construct a 1-round delegation scheme for every language computable in time t = t(n) and space s = s(n), where the running time of the prover is poly(t) and the running time of the verifier is Õ (n + poly(s)) (where Õ hides polylog(t) factors). 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 (cheat- ing) 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) and space s = s(n), we construct MIPs that are sound against no-signaling strategies, where the running time of the provers is poly(t), the number of provers is Õ (s), and the running time of the verifier is Õ (s + n). We then show how to use the method suggested by Aiello et al : (ICALP, 2000) to convert our MIP into a 1-round delegation scheme, by using a computational private information retrieval (PIR) scheme. Thus, assuming the existence of a sub-exponentially secure PIR scheme, we get our 1-round delegation scheme.

KW - Interactive arguments

KW - No-signaling proof-systems

KW - Verifiable delegation

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

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

U2 - 10.1145/2488608.2488679

DO - 10.1145/2488608.2488679

M3 - Conference contribution

AN - SCOPUS:84879827428

SN - 9781450320290

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

SP - 565

EP - 574

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

T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013

Y2 - 1 June 2013 through 4 June 2013

ER -