A practical approach to achieve private medical record linkage in light of public resources

By Mehmet Kuzu, Murat Kantarcioglu, Elizabeth Durham, Csaba Tóth, Bradley A. Malin. 2013

64 citations recorded by the source corpus.

OBJECTIVE Integration of patients' records across resources enhances analytics. To address privacy concerns, emerging strategies such as Bloom filter encodings (BFEs), enable integration while obscuring identifiers. However, recent investigations demonstrate BFEs are, in theory, vulnerable to cryptanalysis when encoded identifiers are randomly selected from a public resource. This study investigates the extent to which cryptanalysis conditions hold for (1) real patient records and (2) a countermeasure that obscures the frequencies of the identifying values in encoded datasets. DESIGN First, to investigate the strength of cryptanalysis for real patient records, we build BFEs from identifiers in an electronic medical record system and apply cryptanalysis using identifiers in a publicly available voter registry. Second, to investigate the countermeasure under ideal cryptanalysis conditions, we compose BFEs from the identifiers that are randomly selected from a public voter registry. MEASUREMENT We utilize precision (ie, rate of correct re-identified encodings) and computation efficiency (ie, time to complete cryptanalysis) to assess the performance of cryptanalysis in BFEs before and after application of the countermeasure. RESULTS Cryptanalysis can achieve high precision when the encoded identifiers are composed of a random sample of a public resource (ie, a voter registry). However, we also find that the attack is less efficient and may not be practical for more realistic scenarios. By contrast, the proposed countermeasure made cryptanalysis impractical in terms of precision and efficiency. CONCLUSIONS Performance of cryptanalysis against BFEs based on patient data is significantly lower than theoretical estimates. The proposed countermeasure makes BFEs resistant to known practical 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

In Management Science and Operations Research

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].”
Cryptanalysis of Basic Bloom Filters Used for Privacy Preserving Record Linkage (2014, background): “However, if there exists at least one bit position that is set to 1 by (at least) one of the hash functions h1(t), . . . , hk(t), but for which the Bloom filter of S shows zero, t definitely does not belong to S.1”
Efficient private record linkage of very large datasets (2013, background): “However, if a random sample of identifiers in the population is available to the attacker, a cryptographic attack on Bloom-Filters might be successful for the most frequent names (see Kuzu et al. 2013).”