Memory delegation

Kai Min Chung, Yael Tauman Kalai, Feng Hao Liu, Ran Raz

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

80 Scopus citations

Abstract

We consider the problem of delegating computation, where the delegator doesn't even know the input to the function being delegated, and runs in time significantly smaller than the input length. For example, consider the setting of memory delegation, where a delegator wishes to delegate her entire memory to the cloud. The delegator may want the cloud to compute functions on this memory, and prove that the functions were computed correctly. As another example, consider the setting of streaming delegation, where a stream of data goes by, and a delegator, who cannot store this data, delegates this task to the cloud. Later the delegator may ask the cloud to compute statistics on this streaming data, and prove the correctness of the computation. We note that in both settings the delegator must keep a (short) certificate of the data being delegated, in order to later verify the correctness of the computations. Moreover, in the streaming setting, this certificate should be computed in a streaming manner. We construct both memory and streaming delegation schemes. We present non-interactive constructions based on the (standard) delegation scheme of Goldwasswer et. al. [GKR08]. These schemes allow the delegation of any function computable by an -uniform circuit of low depth (the complexity of the delegator depends linearly on the depth). For memory delegation, we rely on the existence of a polylog PIR scheme, and for streaming, we rely on the existence of a fully homomorphic encryption scheme. We also present constructions based on the CS-proofs of Micali. These schemes allow the delegation of any function in P. However, they are interactive (i.e., consists of 4 messages), or are non-interactive in the Random Oracle Model.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings
Pages151-168
Number of pages18
DOIs
StatePublished - 2011
Event31st Annual International Cryptology Conference, CRYPTO 2011 - Santa Barbara, CA, United States
Duration: Aug 14 2011Aug 18 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6841 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other31st Annual International Cryptology Conference, CRYPTO 2011
CountryUnited States
CitySanta Barbara, CA
Period8/14/118/18/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Memory delegation'. Together they form a unique fingerprint.

Cite this