Delegation for bounded space

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.