Delegation for bounded space

Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Pages565-574
Number of pages10
DOIs
StatePublished - Jul 11 2013
Externally publishedYes
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
CountryUnited States
CityPalo Alto, CA
Period6/1/136/4/13

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Interactive arguments
  • No-signaling proof-systems
  • Verifiable delegation

Fingerprint Dive into the research topics of 'Delegation for bounded space'. Together they form a unique fingerprint.

  • Cite this

    Kalai, Y. T., Raz, R., & Rothblum, R. D. (2013). Delegation for bounded space. In STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing (pp. 565-574). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488679