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.

[img]
Preview
Text - Published Version
Download (487kB) | Preview

Abstract

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.

Item Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Z Bibliography. Library Science. Information Resources
Divisions: School of Social Sciences > Department of Sociology
URI: http://openaccess.city.ac.uk/id/eprint/14304

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics