Doctoral Thesis: Oblivious RAM (ORAM)


Event Speaker: 

Christopher W. Fletcher

Event Date/Time: 

Wednesday, May 18, 2016 - 1:00pm

Oblivious RAM (ORAM) is a cryptographic primitive that obfuscates a client's access pattern (address, data, read/write) to an untrusted memory source.  In addition to its traditional application to outsourced storage, ORAM has proven to be an important component in the Cryptographic "swiss army knife" -- finding uses in Garbled RAM, Secure Computation, Proofs of Retrievability, and more.

In this talk I will present two ORAM constructions:

First, I will present a bandwidth-efficient ORAM in the traditional ORAM setting (where the server cannot perform computation).

Our construction, Ring ORAM, is currently the most bandwidth efficient ORAM scheme --- also counting constant factors --- in the small client storage setting and can match the bandwidth of large client storage ORAM schemes.

On the theory side, Ring ORAM features a tighter and significantly simpler analysis than prior art. 

Second, I will present the first ORAM scheme, called Onion ORAM, with constant worst-case bandwidth blowup that leverages no more than poly-logarithmic server computation and standard cryptographic assumptions.

In particular, it does not require fully homomorphic encryption, but employs an additively homomorphic encryption scheme such as the Damg\r{a}rd-Jurik cryptosystem or a somewhat homomorphic encryption scheme such as NTRU or R-LWE.

Further, to achieve malicious security our construction does not require expensive and non-standard techniques such as SNARKs, but rather the existence of collision-resistant hash functions.