Oblivious data structures

Xiao Wang, Kartik Nayak, Chang Liu, T. H.Hubert Chan, Elaine Shi, Emil Stefanov, Yan Huang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

40 Scopus citations

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 shortestpath distance queries on weighted planar graphs. Our oblivious counterparts of the above outperform the best known ORAM scheme both asymptotically and in practice. Copyright is held by the owner/author(s). Publication rights licensed to ACM.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Pages215-226
Number of pages12
ISBN (Electronic)9781450329576, 9781450329576, 9781450331470, 9781450331500, 9781450331517, 9781450331524, 9781450331531, 9781450331548, 9781450331555, 9781450332392
DOIs
StatePublished - Nov 3 2014
Event21st ACM Conference on Computer and Communications Security, CCS 2014 - Scottsdale, United States
Duration: Nov 3 2014Nov 7 2014

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Other

Other21st ACM Conference on Computer and Communications Security, CCS 2014
CountryUnited States
CityScottsdale
Period11/3/1411/7/14

    Fingerprint

Keywords

  • Cryptography
  • Oblivious algorithms
  • Security

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Cite this

Wang, X., Nayak, K., Liu, C., Chan, T. H. H., Shi, E., Stefanov, E., & Huang, Y. (2014). Oblivious data structures. In Proceedings of the ACM Conference on Computer and Communications Security (pp. 215-226). (Proceedings of the ACM Conference on Computer and Communications Security). Association for Computing Machinery. https://doi.org/10.1145/2660267.2660314