Bloom Filters and Cryptography
Many efficient data structures use randomness, allowing them to improve upon deterministic ones. Usually, their efficiency or correctness are analyzed using probabilistic tools under the assumption that the inputs and queries are independent of the internal randomness of the data structure.
In this talk, we will consider data structures in a more robust model, which we call the adversarial model. Roughly speaking, this model allows an adversary to choose inputs and queries adaptively according to previous responses. Specifically, we will consider Bloom filters, a data structure for approximate set membership, and prove a tight connection between Bloom filters in this model and cryptography.
Joint work with Eylon Yogev