Cryptology ePrint Archive: Report 2019/632

Fully Homomorphic Encryption for RAMs

Ariel Hamlin and Justin Holmgren and 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.

Category / Keywords: Fully Homomorphic Encryption, Oblivious Ram, Secret-Key Private Information Retrieval, Obfuscation

Original Publication (with major differences): IACR-CRYPTO-2019

Date: received 2 Jun 2019, last revised 17 Jun 2019

Contact author: arihamlin at gmail com,justin holmgren@gmail com,mormorweiss@gmail com,wichs@ccs neu edu

Available format(s): PDF | BibTeX Citation

Version: 20190617:161854 (All versions of this report)

Short URL: ia.cr/2019/632


[ Cryptology ePrint archive ]