Length Leakage in Oblivious Data Access Mechanisms

Grace Jia; Rachit Agarwal; Anurag Khandelwal

Paper 2024/863

Length Leakage in Oblivious Data Access Mechanisms

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.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Major revision. USENIX Security
Contact author(s): grace jia @ yale edu
ragarwal @ cs cornell edu
anurag khandelwal @ yale edu
History: 2024-06-13: revised; 2024-05-31: received; See all versions
Short URL: https://ia.cr/2024/863
License: CC BY

BibTeX

@misc{cryptoeprint:2024/863,
      author = {Grace Jia and Rachit Agarwal and Anurag Khandelwal},
      title = {Length Leakage in Oblivious Data Access Mechanisms},
      howpublished = {Cryptology ePrint Archive, Paper 2024/863},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/863}},
      url = {https://eprint.iacr.org/2024/863}
}