City Research Online

Cryptanalysis of Basic Bloom Filters Used for Privacy Preserving Record Linkage

Niedermeyer, F., Steinmetzer, S., Kroll, M. & Schnell, R. (2014). Cryptanalysis of Basic Bloom Filters Used for Privacy Preserving Record Linkage. Journal of Privacy and Condentiality, 6(2), pp. 59-79.


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.

Publication Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Z Bibliography. Library Science. Information Resources
Departments: School of Policy & Global Affairs > Sociology & Criminology
[thumbnail of Niedermeyer_2014_Cryptanalysis_Of_Basic_Bloom_Filters_Used_For_Privacy_Preserving_Record_Linkage_2.pdf]
Text - Published Version
Download (487kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login