## Memory Delegation

** Kai-Min Chung, Yael Kalai, Feng-Hao Liu, and Ran Raz **

*
Cornell University; Microsoft Research; Brown University; and Weizmann Institute of Science*
**
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.* (STOC ’08).
These schemes allow the delegation of any function computable by
an ${\cal L}$-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.

**
Keywords:** Delegation Schemes, PIR, Fully Homomorphic Encrpytion