### 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 language | English (US) |
---|---|

Title of host publication | STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing |

Pages | 565-574 |

Number of pages | 10 |

DOIs | |

State | Published - Jul 11 2013 |

Externally published | Yes |

Event | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States Duration: Jun 1 2013 → Jun 4 2013 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

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

Country | United States |

City | Palo Alto, CA |

Period | 6/1/13 → 6/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

*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