Length Leakage in Oblivious Data Access Mechanisms

Authors: 

Grace Jia, Yale University; Rachit Agarwal, Cornell University; Anurag Khandelwal, Yale University

Abstract: 

This paper explores the problem of preventing length leakage in oblivious data access mechanisms with passive persistent adversaries. We show that designing mechanisms that prevent both length leakage and access pattern leakage requires navigating a three-way tradeoff between storage footprint, bandwidth footprint, and the information leaked to the adversary. We establish powerful lower bounds on achievable storage and bandwidth footprints for a variety of leakage profiles, and present constructions that perfectly or near-perfectly match the lower bounds.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {299816,
author = {Grace Jia and Rachit Agarwal and Anurag Khandelwal},
title = {Length Leakage in Oblivious Data Access Mechanisms},
booktitle = {33rd USENIX Security Symposium (USENIX Security 24)},
year = {2024},
isbn = {978-1-939133-44-1},
address = {Philadelphia, PA},
pages = {6417--6434},
url = {https://www.usenix.org/conference/usenixsecurity24/presentation/jia-grace},
publisher = {USENIX Association},
month = aug
}

Presentation Video