Rewindable Oblivious RAM and Applications to Fully Homomorphic Encryption for RAMs

Mor Weiss

In this talk I will present rewindable Oblivious RAM (ORAM), which is a strengthening of ORAM which remains secure when an adversarial server rewinds the ORAM client. Using Symmetric-Key Doubly-Efficient PIR (SK-DEPIR) (Canetti-Holmgren-Richelson, Boyle-Ishai-Pass-Wootters: TCC '17) we will construct two flavors of rewindable ORAM: an ORAM scheme with polylogarithmic complexity secure against rewinds to the initial state, and a scheme with sublinear complexity secure against rewinds to any intermediate state. Notice that known ORAM schemes do not retain their security in this rewindable setting.
Using rewindable ORAM, along with virtual black-box obfuscation for specific circuits, we will construct a fully homomorphic encryption scheme for RAM machines. This is a public-key encryption scheme where one can evaluate RAM programs on an encryption of a large database D, where the running time over the encrypted data is “close” to the worst-case running time of the program.

Joint work with Ariel Hamlin, Justin Holmgren and Daniel Wichs; to appear at CRYPTO`19.