Bloom Filters in Adversarial Environments

DOI10.1007/978-3-662-48000-7_28zbMath1369.94560arXiv1412.8356OpenAlexW201721620WikidataQ127732535 ScholiaQ127732535MaRDI QIDQ3457085

Eylon Yogev, Moni Naor, Yogev Eylon

Publication date: 10 December 2015

Published in: Lecture Notes in Computer Science, ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.8356

zbMATH Keywords

pseudorandom functionsBloom filterstreaming algorithmadaptive inputs

Mathematics Subject Classification ID

Cryptography (94A60) Data structures (68P05) Online algorithms; streaming algorithms (68W27)

Related Items

A Framework for Adversarially Robust Streaming Algorithms, Property-preserving hash functions for Hamming distance from standard assumptions, On the optimal succinctness and efficiency of functional encryption and attribute-based encryption, Cuckoo hashing in cryptography: optimal parameters, robustness and applications, Bet-or-pass: adversarially robust Bloom filters, Unnamed Item, Bloom filter encryption and applications to efficient forward-secret 0-RTT key exchange, Robust property-preserving hash functions for Hamming distance and more, Pseudorandom Functions: Three Decades Later

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Explicit and efficient hash families suffice for cuckoo hashing with a stash
• Clocked adversaries for hashing
• On the construction of pseudorandom permutations: Luby-Rackoff revisited
• An algorithm for approximate membership checking with application to password security
• Sliding Bloom Filters
• BLAKE2: Simpler, Smaller, Fast as MD5
• Sketching in Adversarial Environments
• Intel’s New AES Instructions for Enhanced Performance and Security
• Learnability and the Vapnik-Chervonenkis dimension
• Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
• Almost random graphs with simple hash functions
• Uniform Hashing in Constant Time and Optimal Space
• A theory of the learnable
• How to Construct Pseudorandom Permutations from Pseudorandom Functions
• Foundations of Cryptography
• Network Applications of Bloom Filters: A Survey
• Cuckoo hashing
• Hardness Preserving Reductions via Cuckoo Hashing
• Exact and approximate membership testers
• Cache-, hash-, and space-efficient bloom filters
• Sometimes-Recurse Shuffle
• How robust are linear sketches to adaptive inputs?
• Space/time trade-offs in hash coding with allowable errors
• Theory of Cryptography
• Tight bounds for sliding Bloom filters