Efficient cryptanalysis of bloom filters for privacy-preserving record linkage

Peter Christen*, Rainer Schnell, Dinusha Vatsalan, Thilina Ranbaduge

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    49 Citations (Scopus)

    Abstract

    Privacy-preserving record linkage (PPRL) is the process of identifying records that represent the same entity across databases held by different organizations without revealing any sensitive information about these entities. A popular technique used in PPRL is Bloom filter encoding, which has shown to be an efficient and effective way to encode sensitive information into bit vectors while still enabling approximate matching of attribute values. However, the encoded values in Bloom filters are vulnerable to cryptanalysis attacks. Under specific conditions, these attacks are successful in that some frequent sensitive attribute values can be re-identified. In this paper we propose and evaluate on real databases a novel efficient attack on Bloom filters. Our approach is based on the construction principle of Bloom filters of hashing elements of sets into bit positions. The attack is independent of the encoding function and its parameters used, it can correctly re-identify sensitive attribute values even when various recently proposed hardening techniques have been applied, and it runs in a few seconds instead of hours.

    Original languageEnglish
    Title of host publicationAdvances in Knowledge Discovery and Data Mining - 21st Pacific-Asia Conference, PAKDD 2017, Proceedings
    EditorsKyuseok Shim, Jae-Gil Lee, Longbing Cao, Xuemin Lin, Jinho Kim, Yang-Sae Moon
    PublisherSpringer Verlag
    Pages628-640
    Number of pages13
    ISBN (Print)9783319574530
    DOIs
    Publication statusPublished - 2017
    Event21st Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2017 - Jeju, Korea, Republic of
    Duration: 23 May 201726 May 2017

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume10234 LNAI
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference21st Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2017
    Country/TerritoryKorea, Republic of
    CityJeju
    Period23/05/1726/05/17

    Fingerprint

    Dive into the research topics of 'Efficient cryptanalysis of bloom filters for privacy-preserving record linkage'. Together they form a unique fingerprint.

    Cite this