title: Composite Bloom Filters for Secure Record Linkage.
abstract: The process of record linkage seeks to integrate instances that correspond to the same entity. Record linkage has traditionally been performed through the comparison of identifying field values (e.g., Surname), however, when databases are maintained by disparate organizations, the disclosure of such information can breach the privacy of the corresponding individuals. Various private record linkage (PRL) methods have been developed to obscure such identifiers, but they vary widely in their ability to balance competing goals of accuracy, efficiency and security. The tokenization and hashing of field values into Bloom filters (BF) enables greater linkage accuracy and efficiency than other PRL methods, but the encodings may be compromised through frequency-based cryptanalysis. Our objective is to adapt a BF encoding technique to mitigate such attacks with minimal sacrifices in accuracy and efficiency. To accomplish these goals, we introduce a statistically-informed method to generate BF encodings that integrate bits from multiple fields, the frequencies of which are provably associated with a minimum number of fields. Our method enables a user-specified tradeoff between security and accuracy. We compare our encoding method with other techniques using a public dataset of voter registration records and demonstrate that the increases in security come with only minor losses to accuracy.
authors.affiliation: Dept. of Biomedical Informatics, Vanderbilt University, Nashville, TN 37232. ea.durham@vanderbilt.edu.
authors.forename: Elizabeth Ashley
authors.initials: EA
authors.lastname: Durham
authors.affiliation: Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75083. muratk@utdallas.edu.
authors.forename: Murat
authors.initials: M
authors.lastname: Kantarcioglu
authors.affiliation: Dept. of Electrical Engineering & Computer Science, Vanderbilt University, Nashville, TN 37232. yuan.xue@vanderbilt.edu.
authors.forename: Yuan
authors.initials: Y
authors.lastname: Xue
authors.affiliation: Dept. of Biomedical Informatics, Vanderbilt University, Nashville, TN 37232. csaba.toth@vanderbilt.edu.
authors.forename: Csaba
authors.initials: C
authors.lastname: Toth
authors.affiliation: Dept. of Computer Science, University of Texas at Dallas, Richardson, TX, 75083. mehmet.kuzu@utdallas.edu.
authors.forename: Mehmet
authors.initials: M
authors.lastname: Kuzu
authors.affiliation: Depts. of Biomedical Informatics and EECS, Vander bilt University, Nashville, TN 37232. b.malin@vanderbilt.edu.
authors.forename: Bradley
authors.initials: B
authors.lastname: Malin
keywords: Bloom filter; data matching; entity resolution; privacy; record linkage; security