Paper 2019/1221

Probabilistic Data Structures in Adversarial Environments

David Clayton, Christopher Patton, and Thomas Shrimpton


Probabilistic data structures use space-efficient representations of data in order to (approximately) respond to queries about the data. Traditionally, these structures are accompanied by probabilistic bounds on query-response errors. These bounds implicitly assume benign attack models, in which the data and the queries are chosen non-adaptively, and independent of the randomness used to construct the representation. Yet probabilistic data structures are increasingly used in settings where these assumptions may be violated. This work provides a provable-security treatment of probabilistic data structures in adversarial environments. We give a syntax that captures a wide variety of in-use structures, and our security notions support derivation of error bounds in the presence of powerful attacks. We use our formalisms to analyze Bloom filters, counting (Bloom) filters and count-min sketch data structures. For the traditional version of these, our security findings are largely negative; however, we show that simple embellishments (e.g., using salts or secret keys) yields structures that provide provable security, and with little overhead.

Available format(s)
Publication info
Published elsewhere. MINOR revision.ACM CCS
data structureshash functions
Contact author(s)
davidclayton @ ufl edu
2019-10-21: received
Short URL
Creative Commons Attribution


      author = {David Clayton and Christopher Patton and Thomas Shrimpton},
      title = {Probabilistic Data Structures in Adversarial Environments},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1221},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.