Cryptanalysis of Basic Bloom Filters Used for Privacy Preserving Record Linkage
By Frank Niedermeyer, Simone Steinmetzer, Martin Kroll, R. Schnell. 2014
100 citations recorded by the source corpus.
Bloom filter encoded identifiers are increasingly used for privacy preserving record linkage applications, because they allow for errors in encrypted identifiers. However, little research on the security of Bloom filters has been published so far. In this paper, we formalize a successful attack on Bloom filters composed of bigrams. It has previously been assumed in the literature that an attacker knows the global data set from which a sample is drawn. In contrast, we suppose that an attacker does not know this global data set. Instead, we assume the adversary knows a publicly available list of the most frequent attributes. The attack is based on subtle filtering and elementary statistical analysis of encrypted bigrams. The attack described in this paper can be used for the deciphering of a whole database instead of only a small subset of the most frequent names, as in previous research. We illustrate our proposed method with an attack on a database of encrypted surnames. Finally, we describe modifications of the Bloom filters for preventing similar attacks.
Subfields: Artificial Intelligence, Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Richard Nock
- Giorgio Patrini
- Stephen Hardy
- Hamish Ivey-Law
- Brian Thorne
- Guillaume Smith
- Wilko Henecka
- Qiang Yang
In Management Science and Operations Research
- Hamish Ivey-Law
- Richard Nock
- Stephen Hardy
- Brian Thorne
- Guillaume Smith
- Wilko Henecka
- Giorgio Patrini
Citations in the corpus
- Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption (2017, background): “Hence the longer dataset is truncated, excluding only non-matched entities.2 1While CLKs are robust to typographical errors, they are susceptible to cryptanalytic attacks if insecure parameters are used, or if too few identifiers are hashed [Kuzu et al., 2011, 2013, Niedermeyer et al., 2014].”