Oblivious Data Structures
Authors:
Open Access
- 3 November 2014
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 215-226
Abstract
We design novel, asymptotically more efficient data structures and algorithms for programs whose data access patterns exhibit some degree of predictability. To this end, we propose two novel techniques, a pointer-based technique and a locality-based technique. We show that these two techniques are powerful building blocks in making data structures and algorithms oblivious. Specifically, we apply these techniques to a broad range of commonly used data structures, including maps, sets, priority-queues, stacks, deques; and algorithms, including a memory allocator algorithm, max-flow on graphs with low doubling dimension, and shortest-path distance queries on weighted planar graphs. Our oblivious counterparts of the above outperform the best known ORAM scheme both asymptotically and in practice.Keywords
Funding Information
- Alfred P. Sloan Foundation
- Research Grants Council, University Grants Committee, Hong Kong (HKU719312E)
- Division of Computer and Network Systems (CNS-1314857)
- Defense Advanced Research Projects Agency (FA8750-14-C-0057)
This publication has 49 references indexed in Scilit:
- How to Garble RAM Programs?2013
- Optimizing ORAM and Using It Efficiently for Secure Computation2013
- Random sampling from a search engine's indexJournal of the ACM, 2008
- HIDEACM SIGPLAN Notices, 2004
- HIDEACM SIGARCH Computer Architecture News, 2004
- Architectural support for copy and tamper resistant softwareACM SIGARCH Computer Architecture News, 2000
- Software protection and simulation on oblivious RAMsJournal of the ACM, 1996
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Relations Among Complexity MeasuresJournal of the ACM, 1979
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956