Paper 2019/632

Fully Homomorphic Encryption for RAMs

Ariel Hamlin, Justin Holmgren, Mor Weiss, and Daniel Wichs


We initiate the study of fully homomorphic encryption for RAMs (RAM-FHE). This is a public-key encryption scheme where, given an encryption of a large database $D$, anybody can efficiently compute an encryption of $P(D)$ for an arbitrary RAM program $P$. The running time over the encrypted data should be as close as possible to the worst case running time of $P$, which may be sub-linear in the data size. A central difficulty in constructing a RAM-FHE scheme is hiding the sequence of memory addresses accessed by $P$. This is particularly problematic because an adversary may homomorphically evaluate many programs over the same ciphertext, therefore effectively ``rewinding'' any mechanism for making memory accesses oblivious. We identify a necessary prerequisite towards constructing RAM-FHE that we call \emph{rewindable oblivious RAM} (rewindable ORAM), which provides security even in this strong adversarial setting. We show how to construct rewindable ORAM using \emph{symmetric-key doubly efficient PIR (SK-DEPIR)} (Canetti-Holmgren-Richelson, Boyle-Ishai-Pass-Wootters: TCC '17). We then show how to use rewindable ORAM, along with virtual black-box (VBB) obfuscation for specific circuits, to construct RAM-FHE. The latter primitive can be heuristically instantiated using existing indistinguishability obfuscation candidates. Overall, we obtain a RAM-FHE scheme where the multiplicative overhead in running time is polylogarithmic in the data size $N$. Our basic scheme is single-hop, but we also extend it to get multi-hop RAM-FHE with overhead $N^\epsilon$ for arbitrarily small $\epsilon>0$. We view our work as the first evidence that RAM-FHE is likely to exist.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2019
Fully Homomorphic EncryptionOblivious RamSecret-Key Private Information RetrievalObfuscation
Contact author(s)
arihamlin @ gmail com
justin holmgren @ gmail com
mormorweiss @ gmail com
wichs @ ccs neu edu
2019-06-17: revised
2019-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ariel Hamlin and Justin Holmgren and Mor Weiss and Daniel Wichs},
      title = {Fully Homomorphic Encryption for RAMs},
      howpublished = {Cryptology ePrint Archive, Paper 2019/632},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.