Adversarial Correctness and Privacy for Probabilistic Data Structures
Mia Filić, Kenneth G. Paterson, Anupama Unnikrishnan, Fernando Virdia · Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security · 2022
We study the security of Probabilistic Data Structures (PDS) for handling Approximate Membership Queries (AMQ); prominent examples of AMQ-PDS are Bloom and Cuckoo filters. AMQ-PDS are increasingly being deployed in environments where adversaries can gain benefit from carefully selecting inputs, for example to increase the false positive rate of an AMQ-PDS. They are also being used in settings where the inputs are sensitive and should remain private in the face of adversaries who can access an AMQ-PDS through an API or who can learn its internal state by compromising the system running the AMQ-PDS.