Cryptology ePrint Archive: Report 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 P with security parameter k, the cloud runs in time $T \cdot \poly(k)$ and the user in time $\poly(|P|, \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.

Category / Keywords:

Date: received 1 Oct 2015, last revised 6 Oct 2015

Contact author: omerpa at gmail com, yael@microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20151006:204900 (All versions of this report)

Short URL: ia.cr/2015/957

Discussion forum: Show discussion | Start new discussion