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