UMBC ebiquity

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

Authors: Daniel S Roche, Adam Aviv, and SeungGeol Choi

Book Title: IEEE Symposium on Security and Privacy

Date: May 01, 2016

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 218 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).

Type: InProceedings

Publisher: IEEE

Tags: security, privacy

Google Scholar: search

Number of downloads: 266


Available for download as

size: 538004 bytes

Related Projects:

Active Project

 Secure and Oblivious Cloud Storage and Deletion.