Paper 2019/632

Fully Homomorphic Encryption for RAMs

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

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2019
Keywords
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
History
2019-06-17: revised
2019-06-03: received
See all versions
Short URL
https://ia.cr/2019/632
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/632,
      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},
      url = {https://eprint.iacr.org/2019/632}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.