Privacy-preserving record linkage using Bloom filters

By R. Schnell, Tobias Bachteler, Jörg Reiher. BMC Medical Informatics Decis. Mak., 2009

301 citations recorded by the source corpus.

BackgroundCombining multiple databases with disjunctive or additional information on the same person is occurring increasingly throughout research. If unique identification numbers for these individuals are not available, probabilistic record linkage is used for the identification of matching record pairs. In many applications, identifiers have to be encrypted due to privacy concerns.MethodsA new protocol for privacy-preserving record linkage with encrypted identifiers allowing for errors in identifiers has been developed. The protocol is based on Bloom filters on q-grams of identifiers.ResultsTests on simulated and actual databases yield linkage results comparable to non-encrypted identifiers and superior to results from phonetic encodings.ConclusionWe proposed a protocol for privacy-preserving record linkage with encrypted identifiers allowing for errors in identifiers. Since the protocol can be easily enhanced and has a low computational burden, the protocol might be useful for many applications requiring privacy-preserving record linkage.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/8392fa13e5013073b617e947b0229bf1734990ac

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

In Management Science and Operations Research

Citations in the corpus

A taxonomy of privacy-preserving record linkage techniques (2013, methodology): “’s Bloom filters approach [114] in their work to evaluate three different PPRL approaches.”
Cryptanalysis of Basic Bloom Filters Used for Privacy Preserving Record Linkage (2014, methodology): “One of the most widely used techniques is based on Bloom filters [19].”
Efficient private record linkage of very large datasets (2013, methodology): “In 2009, we suggested the use of Bloom-Filters for cryptographic encoding of identifiers (Schnell et al. 2009).”
Mining Frequent Patterns with Differential Privacy (2013, methodology): “There are several techniques to solve this problem, and they are grouped into tree major families: Secure Multiparty Computation (SMC) [17, 24], secure transformation [2, 7, 19, 20], and hybrid methods [12, 23, 13, 15].”
Assessing the Magnitude of Non-Consent Biases in Linked Survey and Administrative Data (2012, methodology): “…identifying suitable linkage variables, efficient linkage algorithms, and statistical matching techniques is well developed (Scheuren and Winkler 1993; Lahiri and Larsen 2005; Winkler 2006; Chambers 2009; Schnell et al. 2009), studying the impact of linkage non-consent has received less attention.”
A Constraint Satisfaction Cryptanalysis of Bloom Filters in Private Record Linkage (2011, methodology): “In the BFE model described in [12], S is represented as the set of substrings of length n, or n-grams such that QS = {q1, .”
Efficient Similarity Search over Encrypted Data (2012, methodology): “Translation of strings into the Bloom filter encodings is widely used for similarity measurement in the context of private record linkage [20].”
Data Matching (2012, methodology): “[239] presented a three-party protocol using such a Bloom filter approach, and they showed that precision and recall results can be achieved using encrypted Bloom filters that are close to the results that can be achieved with unencoded q-grams.”
Challenges in administrative data linkage for research (2017, methodology): “Bloom filters are more complex data structures than standard hashing functions, and although they preserve anonymity, can be compared using a similarity index such as the Dice coefficient (Schnell et al., 2009).”
A Novel Error-Tolerant Anonymous Linking Code (2011, methodology): “In [13] we suggested to use Bloom filters for calculating string similarities between two strings in a privacy-preserving manner.”
Privacy-Preserving Record Linkage (2010, background): “The question of non-exact matching is partially addressed in [5, 6, 34].”
A practical approach to achieve private medical record linkage in light of public resources (2013, methodology): “This BFE setting was suggested in an earlier study.(30) In the first setting, we composed a real attack scenario, such that the VEMR and DCVR were applied as the sample BFE and global public datasets, respectively.”