Towards Practical Oblivious RAM

Author(s): Emil Stefanov, Elaine Shi and Dawn Song

Download: Paper (PDF)

Date: 6 Feb 2012

Document Type: Briefing Papers

Associated Event: NDSS Symposium 2012

Abstract:

We investigate techniques for making Oblivious RAM practical. We propose an O-RAM construction achieving an overhead of 20-35X, about 63 times faster than the best existing scheme. We employ a novel technique called partitioning, which allows us to break down the O-RAM problem into smaller instances. Our construction also achieves poly-logarithmic worst-case cost.