Paper 2015/1126

A Practical Oblivious Map Data Structure with Secure Deletion and History Independence

Daniel S. Roche, Adam J. Aviv, and Seung Geol Choi

Abstract

We present a new oblivious RAM that supports variable-sized storage blocks (vORAM), which is the first ORAM to allow varying block sizes without trivial padding. We also present a new history-independent data structure (a HIRB tree) that can be stored within a vORAM. Together, this construction provides an efficient and practical oblivious data structure (ODS) for a key/value map, and goes further to provide an additional privacy guarantee as compared to prior ODS maps: even upon client compromise, deleted data and the history of old operations remain hidden to the attacker. We implement and measure the performance of our system using Amazon Web Services, and the single-operation time for a realistic database (up to $2^{18}$ entries) is less than 1 second. This represents a 100x speed-up compared to the current best oblivious map data structure (which provides neither secure deletion nor history independence) by Wang et al. (CCS 14).

Note: Fixed missing references.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
oblivious RAMORAMoblivious data structuresODSsecure deletion
Contact author(s)
roche @ usna edu
History
2015-11-22: revised
2015-11-22: received
See all versions
Short URL
https://ia.cr/2015/1126
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1126,
      author = {Daniel S.  Roche and Adam J.  Aviv and Seung Geol Choi},
      title = {A Practical Oblivious Map Data Structure with Secure Deletion and History Independence},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/1126},
      year = {2015},
      url = {https://eprint.iacr.org/2015/1126}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.