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

Explore a groundbreaking 21-minute conference talk on a new oblivious RAM supporting variable-sized storage blocks (vORAM) and a history-independent data structure (HIRB tree). Delve into the innovative combination that creates an efficient and practical oblivious data structure (ODS) for key/value maps, offering enhanced privacy guarantees. Learn how this construction ensures deleted data and operation history remain hidden even upon client compromise. Discover the impressive performance improvements, with single-operation times under 1 second for realistic databases up to 256K entries, representing a 100x speed-up compared to previous oblivious map data structures. Gain insights into the implementation and performance measurements conducted using Amazon Web Services, and understand the implications for secure and efficient data management in privacy-sensitive applications.