Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM
Ling Ren
Abstract:
Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to store private data on an untrusted server and guarantees that the server learns nothing about the data or the client’s access pattern (the sequence of addresses or operations). Since its initial proposal, ORAM has been studied in various applications including outsourced storage, secure processors and secure multi-party computation. The ORAM model considered historically assumed that the server is a simple storage device that only supports read and write operations. However, in many scenarios the untrusted server has significant computational power. It is natural to extend the ORAM model to allow server computation. An important consequence of this extended ORAM definition is that it renders the well-known Goldreich-Ostrovsky logarithmic lower bound on bandwidth blowup inapplicable.
In this talk, I will present Onion ORAM, the first ORAM construction that achieves constant bandwidth blowup without using fully homomorphic encryption. Instead, our construction employs an additively homomorphic encryption scheme or a somewhat homomorphic encryption scheme without bootstrapping. At the core of our construction is a new ORAM scheme that has "shallow circuit depth" over the entire history of ORAM accesses. I will also present novel techniques to achieve security against a malicious server, without resorting to expensive techniques such as SNARKs.
Joint work with Srinivas Devadas, Marten van Dijk, Christopher Fletcher, Elaine Shi and Daniel Wichs.
Bio:
Ling Ren is a PhD candidate at Electrical Engineering and Computer Science at MIT. His research interest is in computer security and applied cryptography. He obtained his bachelor's degree from Tsinghua University.