- We describe two optimizations to the tree-based ORAM protocol of Shi et al., one reducing the storage overhead of that protocol by an $O(k)$ multiplicative factor, and another reducing its time complexity by an $O(\log k)$ multiplicative factor, where $k$ is the security parameter. Our scheme also enjoys a much simpler and tighter analysis than the original protocol.
- We describe a protocol for binary search over this ORAM construction, where the entire binary search operation is done in the same complexity as a single ORAM access (as opposed to $\log n$ accesses for the naive protocol). We then describe simple uses of this binary-search protocol for things like range queries and keyword search.
- We show how the ORAM protocol itself and our binary-search protocol can be implemented efficiently as secure computation, using somewhat-homomorphic encryption.
Since memory accesses by address (ORAM access) or by value (binary search) are basic and prevalent operations, we believe that these optimizations can be used to significantly speed-up many higher-level protocols for secure computation.Category / Keywords: cryptographic protocols / oblivious RAM Publication Info: Full version of a PETS (privacy-enhancing technologies) 2013 paper. Date: received 28 Apr 2013 Contact author: wichs at ccs neu edu Available format(s): PDF | BibTeX Citation Version: 20130429:113625 (All versions of this report) Discussion forum: Show discussion | Start new discussion