Welcome to the resource topic for 2022/1186
Title:
Adversarial Correctness and Privacy for Probabilistic Data Structures
Authors: Mia Filić, Kenneth G. Paterson, Anupama Unnikrishnan, Fernando Virdia
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.
ePrint: https://eprint.iacr.org/2022/1186
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .