Paper 2025/1636

Differentially Private Access in Encrypted Search: Achieving Privacy at a Small Cost?

Abstract

Encrypted search focuses on protecting sensitive data in outsourced environments while enabling private queries. Although standard encrypted search algorithms are efficient, they often leak some information about the queries and data. One such leakage is the access pattern on the outsourced storage. Recent leakage-abuse attacks have exploited this seemingly harmless leakage to successfully recover both queries and data, shifting research priorities towards finding the right balance between privacy and performance. While some proposals leverage oblivious RAM or other oblivious data structures to hide the access pattern, they typically incur significant bandwidth costs. In response, researchers have developed new schemes that ensure access leakage satisfies differential privacy (DP). Yet the security implications of these new guarantees remain unclear. Especially, compared with conventional differential privacy, the application and threat model are significantly different. To understand these implications, we investigate two concrete instances of (encrypted) range-query schemes (appeared in SODA ’19 and CCS ’22) that achieve differentially private access. We analyze their security guarantees using inference attacks to recover queries and data on real-world datasets. Our findings raise a critical concern that ensuring access leakage is differentially private either falls short of providing strong security for the queries and data, diverging from the initial goals, or offers only weak security but at a high efficiency/correctness cost. As part of our analysis, we also propose a generic security definition for DP access, and identify two general techniques for leakage mitigation, bucketization and partitioning, that may be of independent interest.