Breaking BAD? Better Call SAUL! - Breaking and Fixing Bloom Filters with Added Diffusion
Authors: Frederik Armknecht (University of Mannheim), Jochen Schäfer (University of Mannheim)
Volume: 2026
Issue: 2
Pages: 6–19
DOI: https://doi.org/10.56553/popets-2026-0033
Abstract: Merging records from two databases by comparing quasi-identifiers such as names or addresses is a frequently occurring task in many academic and administrative domains. Privacy-Preserving Record Linkage (PPRL) techniques aim to provide a way of computing the similarities between quasi-identifiers without revealing the plaintext data. In practice, PPRL is usually performed by applying a similarity-preserving encoding to the data and comparing similarities on the encoded data only. However, recent research demonstrated that all standard PPRL encoding schemes, with the exception of Bloom filters with added diffusion (BAD), are vulnerable to Graph Matching Attacks and should no longer be considered secure. In this paper, we identify two properties of BAD that leak information about the plaintext to an attacker. We then proceed to show that these leaks make BAD vulnerable to an adapted variant of graph matching attacks. The newly proposed Homomorphism-based Graph Matching Attack is capable of re-identifying up to 91.6% of BAD-encoded records, thereby breaking the only remaining secure encoding scheme. As a remedy, we present a new Scheme for Anonymous, Utility-preserving Linkage (SAUL), which is not only robust against our new attack and all previous ones, but also outperforms the state of the art in terms of linkage quality.
Keywords: privacy-preserving record linkage, graph matching attacks, bloom filters, homomorphism
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
