Abstract
Being able to identify records that correspond to the same entity across databases is important in data analytics. Privacy-preserving record linkage (PPRL) are techniques that can link records such that besides the record pairs classified as matches no sensitive information about the entities in the linked databases is revealed. A popular technique used in PPRL is to encode sensitive values into Bloom filters, which allows approximate matching using character q-grams. PPRL based on Bloom filter encoding has shown to be accurate and scalable to large databases. However, studies have shown that Bloom filters used for PPRL are vulnerable to attacks that can re-identify sensitive values. While previous attack methods were slow and required knowledge of encoding parameters, we present a novel attack which exploits how values are encoded into Bloom filters. Our attack does not require knowledge of the encoding function or its parameter settings used. It is able to correctly re-identify q-grams that could not have been hashed to certain Bloom filter bit positions, Using these re-identified q-grams it can then re-identify attribute values with high precision. Our method is faster than earlier attacks and it can successfully re-identify attribute values from large databases in a few minutes.
Funding Information
  • Simons Foundation
  • Australian Research Council (DP130101801)

This publication has 26 references indexed in Scilit: