City Research Online

Cryptanalysis of Basic Bloom Filters Used for Privacy Preserving Record Linkage

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

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.

Publication Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Z Bibliography. Library Science. Information Resources
Departments: School of Arts & Social Sciences > Sociology
URI: http://openaccess.city.ac.uk/id/eprint/14304
[img]
Preview
Text - Published Version
Download (487kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login