Towards Practical Oblivious RAM
Download: Paper (PDF)
Date: 6 Feb 2012
Document Type: Briefing Papers
Associated Event: NDSS Symposium 2012
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.