  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 definitions 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.
