Paper 2019/1221

Probabilistic Data Structures in Adversarial Environments

David Clayton, Christopher Patton, and Thomas Shrimpton

Abstract

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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. MINOR revision.ACM CCS
Keywords
data structureshash functions
Contact author(s)
davidclayton @ ufl edu
History
2019-10-21: received
Short URL
https://ia.cr/2019/1221
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1221,
      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{https://eprint.iacr.org/2019/1221}},
      url = {https://eprint.iacr.org/2019/1221}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.