Hardened Bloom Filters, with an Application to Unobservability

Nicolas Bernard, Franck Leprévost


Classical Bloom filters may be used to elegantly check if an element e belongs to a set S, and, if not, to add e to S. They do not store any data and only provide boolean answers regarding the membership of a given element in the set, with some probability of false positive answers. Bloom filters are often used in caching system to check that some requested data actually exist before doing a costly lookup to retrieve them. However, security issues may arise for some other applications where an active attacker is able to inject data crafted to degrade the filters’ algorithmic properties, resulting for instance in a Denial of Service (DoS) situation. This leads us to the concept of hardened Bloom filters, combining classical Bloom filters with cryptographic hash functions and secret nonces. We show how this approach is successfully used in the TrueNyms unobservability system and protects it against replay attacks.

Full Text:


DOI: http://dx.doi.org/10.2478/v10065-012-0018-y
Data publikacji: 2012-01-01 00:00:00
Data złożenia artykułu: 2016-04-28 09:08:30


Total abstract view - 366
Downloads (from 2020-06-17) - PDF - 0



  • There are currently no refbacks.

Copyright (c) 2015 Annales UMCS Sectio AI Informatica

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.