Paper 2022/1186

Adversarial Correctness and Privacy for Probabilistic Data Structures

Mia Filić, ETH Zurich
Kenneth G. Paterson, ETH Zurich
Anupama Unnikrishnan, ETH Zurich
Fernando Virdia, Intel Labs
Abstract

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. We develop simulation-based security definitions that speak to correctness and privacy of AMQ-PDS. Our definitions are general and apply to a broad range of adversarial settings. We use our defi- nitions to analyse the behaviour of both Bloom filters and insertion- only Cuckoo filters. We show that these AMQ-PDS can be provably protected through replacement or composition of hash functions with keyed pseudorandom functions in their construction. We also examine the practical impact on storage size and computation of providing secure instances of Bloom and insertion-only Cuckoo filters.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. ACM CCS '22
Keywords
probabilistic data structures simulation-based proofs Bloom filters Cuckoo filters
Contact author(s)
mia filic @ inf ethz ch
kenny paterson @ inf ethz ch
anupama unnikrishnan @ inf ethz ch
fernando virdia @ intel com
History
2022-09-09: approved
2022-09-09: received
See all versions
Short URL
https://ia.cr/2022/1186
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1186,
      author = {Mia Filić and Kenneth G. Paterson and Anupama Unnikrishnan and Fernando Virdia},
      title = {Adversarial Correctness and Privacy for Probabilistic Data Structures},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1186},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1186}},
      url = {https://eprint.iacr.org/2022/1186}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.