In this paper, we show how to construct efficient GRAM without circularity and based solely on the existence of any one-way function. The novel approach that allows us to break the circularity is a modification of the Goldreich-Goldwasser-Micali (PRF) construction. More specifically, we modify the PRF to allow PRF-keys to be "adaptively revoked" during run-time at the additive cost of roughly log n per revocation. Then, to improve the overhead of this scheme, we apply a delicate recursion technique that bootstraps mini-GRAM schemes into larger, more powerful ones while still avoiding circularity in the hybrid arguments. This results in secure GRAM with overhead of poly($k$)(min($t; n^\eps$)) for any constant $\eps>0$, where $n$ is the size of memory and $t$ is the running time.
In a companion work (Part I), Gentry, Halevi, Raykova, and Wichs show an alternative approach using identity-based encryption to solve the circularity problem. Their scheme achieves overhead of poly($k$)polylog($n$) assuming the existence of IBE.
Category / Keywords: foundations / Secure Computation, Oblivious RAM, Garbled RAM, Garbled Circuits Original Publication (with major differences): IACR-EUROCRYPT-2014 Date: received 5 Feb 2014 Contact author: stevelu8 at gmail com Available format(s): PDF | BibTeX Citation Note: A merged version of this work and Part I appears in Eurocrypt 2014 Version: 20140205:144429 (All versions of this report) Short URL: ia.cr/2014/083