A graph traversal attack on Bloom filter-based medical data aggregation. (2017)

• Record Type: Journal Article
• Authors: Mitchell, William; Dewri, Rinku; Thurimella, Ramakrishna; Roschke, Max
• Is Part Of: International journal of big data intelligence. Volume 4:Number 4(2017)
• Page Start: 217
• Page End: 226
• Publication Date: 2017
• Subjects: Bloom filter encoding -- BFE -- privacy-preserving record linkage -- PPRL -- medical data aggregation -- cryptanalysis -- two-party linkage -- private record linkage -- PRL; Big data -- Periodicals; 005.705
• Languages: English
• ISSNs: 2053-1389

Abstract

We present a novel cryptanalytic method based on graph traversals to show that record linkage using Bloom filter encoding does not preserve privacy in a two-party setting. Bloom filter encoding is often suggested as a practical approach to medical data aggregation. This attack is stronger than a simple dictionary attack in that it does not assume knowledge of the universe. The attack is very practical and produced accurate results when experimented on large amounts of name-like data derived from a North Carolina voter registration database. We also give theoretical arguments that show that going from bigrams to n-grams, n > 2, does not increase privacy; on the contrary, it actually makes the attack more effective. Finally, some ways to resist this attack are suggested.