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