Sprinkle Differential Privacy on a Bit of Everything

No ratings

Presented at Real World Crypto 2026 by

Daniel Pöllmann

Tianxin Tang

In recent years, differential privacy (DP) has been applied beyond statistical data release to strengthen the privacy guarantees of various systems, but the resulting privacy guarantees in these settings are rarely scrutinized. We show that simply adding DP to a system may not deliver the expected protections, because DP’s guarantees can misalign with the security and privacy requirements of the system it is intended to enhance. As a case study, we analyze two searchable-encryption schemes that claim that their access-pattern leakage satisfies differential privacy and thereby offer strong privacy guarantees with better utility than fully oblivious alternatives. Unfortunately, these schemes fail to achieve their goals: we mount inference attacks that approximately reconstruct the underlying datasets, showing that they fall short of their stated privacy claims while still satisfying the DP notion. This suggests that applying a privacy notion outside its intended context can fail to provide meaningful semantic security and much care must be taken when constructing such systems.