Paper 2015/957

Delegating RAM Computations

Yael Tauman Kalai and Omer Paneth

Abstract

In the setting of cloud computing a user wishes to delegate its data, as well as computations over this data, to a cloud provider. Each computation may read and modify the data, and these modifications should persist between computations. Minding the computational resources of the cloud, delegated computations are modeled as RAM programs. In particular, the delegated computations' running time may be sub-linear, or even exponentially smaller than the memory size. We construct a two-message protocol for delegating RAM computations to an untrusted cloud. In our protocol, the user saves a short digest of the delegated data. For every delegated computation, the cloud returns, in addition to the computation's output, the digest of the modified data, and a proof that the output and digest were computed correctly. When delegating a T-time RAM computation M with security parameter k, the cloud runs in time Poly(T,k) and the user in time Poly(|M|, log T, k). Our protocol is secure assuming super-polynomial hardness of the Learning with Error (LWE) assumption. Security holds even when the delegated computations are chosen adaptively as a function of the data and output of previous computations. We note that RAM delegation schemes are an improved variant of memory delegation schemes [Chung et al. CRYPTO 2011]. In memory delegation, computations are modeled as Turing machines, and therefore, the cloud's work always grows with the size of the delegated data.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
omerpa @ gmail com
yael @ microsoft com
History
2017-05-18: last of 2 revisions
2015-10-02: received
See all versions
Short URL
https://ia.cr/2015/957
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/957,
      author = {Yael Tauman Kalai and Omer Paneth},
      title = {Delegating {RAM} Computations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/957},
      year = {2015},
      url = {https://eprint.iacr.org/2015/957}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.