Cryptology ePrint Archive: Report 2019/1221
Probabilistic Data Structures in Adversarial Environments
David Clayton and 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.
Category / Keywords: applications / data structures, hash functions
Original Publication (with minor differences): ACM CCS
Date: received 17 Oct 2019
Contact author: davidclayton at ufl edu
Available format(s): PDF | BibTeX Citation
Version: 20191021:081924 (All versions of this report)
Short URL: ia.cr/2019/1221
[ Cryptology ePrint archive ]