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.
Category / Keywords: Date: received 1 Oct 2015, last revised 18 May 2017 Contact author: omerpa at gmail com, yael@microsoft com Available format(s): PDF | BibTeX Citation Version: 20170518:181955 (All versions of this report) Short URL: ia.cr/2015/957