Oblivious Data Structures

Authors:

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.
Funding Information
  • Alfred P. Sloan Foundation
  • Research Grants Council, University Grants Committee, Hong Kong (HKU719312E)
  • Google
  • 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: