Precise and Fast Cryptanalysis for Bloom Filter Based Privacy-Preserving Record Linkage
- 4 October 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 31 (11) , 2164-2177
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.Keywords
Funding Information
- Simons Foundation
- Australian Research Council (DP130101801)
This publication has 26 references indexed in Scilit:
- A hybrid private record linkage scheme: Separating differentially private synopses from matching records2015
- Scalable Privacy-Preserving Record Linkage for Multiple Databases2014
- Privacy-preserving record linkage on large real world datasetsJournal of Biomedical Informatics, 2014
- A Graph Matching Method for Historical Census Household LinkageLecture Notes in Computer Science, 2014
- A taxonomy of privacy-preserving record linkage techniquesInformation Systems, 2013
- A practical approach to achieve private medical record linkage in light of public resourcesJournal of the American Medical Informatics Association, 2013
- Privacy-Preserving Record Linkage2010
- Privacy-preserving record linkage using Bloom filtersBMC Medical Informatics and Decision Making, 2009
- Less Hashing, Same Performance: Building a Better Bloom Filter2006
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970