What Storage Access Privacy is Achievable with Small Overhead?

Summary: Shows constant-overhead access requires ε = Ω(log n) differential privacy, implying small-overhead schemes must accept logarithmic leakage. Gives matching DP-ORAM/PIR (ε=Θ(log n), O(1) overhead) and a DP key-value store (ε=Θ(log n), O(log log n) overhead) using oblivious two-choice hashing. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1757
Venue: PODS
Year: 2019
Pagerank: 5.2763118e-05
Overall Rank: 5,911 | 58.88%
DOI: 10.1145/3294052.3319695

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,489	Waffle: An Online Oblivious Datastore for Protecting Data Access Patterns	2023	SIGMOD	4.3341665e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,599	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9973567e-05
10,354	Private Synthetic Data Generation in Bounded Memory	2025	PODS	4.1945683e-05
8,539	Efficient Searchable Encryption Through Compression	2018	VLDB	4.4937074e-05
8,532	Frequency-Hiding Order-Preserving Encryption with Small Client Storage	2021	VLDB	4.4937074e-05
10,916	History-Independent Dynamic Partitioning: Achieving Operation-Order Privacy in Ordered Data Structures	2024	PODS	4.1945683e-05
136	Revealing Information while Preserving Privacy	2003	PODS	0.0004241101
13,118	Access Control for Information-Theoretically Secure Data	2025	VLDB	-
5,278	A Comparative Evaluation of Order-Revealing Encryption Schemes and Secure Range-Query Protocols	2019	VLDB	5.5903398e-05
10,869	Towards Practical Oblivious Map	2025	VLDB	4.1945683e-05
5,754	Oblivious RAM: A Dissection and Experimental Evaluation	2016	VLDB	5.3403422e-05