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:

[ Cryptology ePrint archive ]