Breaking BAD? Better Call SAUL! -- Breaking and Fixing Bloom Filters with Added Diffusion

Frederik Armknecht (Paper author · University of Mannheim), Jochen Schäfer (Paper author · University of Mannheim)

Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 2 · Alpaca

Overview

In this compelling talk from PETS, researchers from the University of Mannheim presented a critical analysis of existing privacy-preserving record linkage (PPRL) schemes, specifically targeting the widely adopted Bloom filter similarity fusion (BFSF) method. The presentation, delivered by a speaker who introduced himself as Robin, on behalf of authors Frederik Armknecht and Jochen Schäfer, unveiled significant vulnerabilities in BFSF, demonstrating how what was previously considered a robust defense against re-identification attacks can be systematically broken. The core of their discovery lies in the subtle ways linearity can emerge in seemingly non-linear cryptographic constructions under typical operating parameters, leading to unexpected information leakage.

Watch on YouTube · Slides

Visual summary for Breaking BAD? Better Call SAUL! -- Breaking and Fixing Bloom Filters with Added Diffusion by Frederik Armknecht, Jochen Schäfer
Visual summary for Breaking BAD? Better Call SAUL! -- Breaking and Fixing Bloom Filters with Added Diffusion by Frederik Armknecht, Jochen Schäfer

Key moments

  1. 0:00 Introduction: Linking sensitive databases securely
  2. 2:00 Graph isomorphism attacks on similarity-preserving encodings
  3. 3:30 Bloom Filter Similarity Fusion (BFSF) scheme
  4. 4:40 Identifying BFSF's linear fusion layer vulnerability
  5. 6:00 The homomorphism-based arithmetic attack against BFSF
  6. 8:00 Introducing 'Solomon' as a new secure solution
  7. 9:20 Solomon's security properties and practical utility

Breaking BAD? Better Call SAUL! -- Breaking and Fixing Bloom Filters with Added Diffusion

Speakers: Frederik Armknecht, Paper author, University of Mannheim; Jochen Schäfer, Paper author, University of Mannheim

Conference: PETS

YouTube: https://www.youtube.com/watch?v=xXxuBTMaIJ0

Overview

In this compelling talk from PETS, researchers from the University of Mannheim presented a critical analysis of existing privacy-preserving record linkage (PPRL) schemes, specifically targeting the widely adopted Bloom filter similarity fusion (BFSF) method. The presentation, delivered by a speaker who introduced himself as Robin, on behalf of authors Frederik Armknecht and Jochen Schäfer, unveiled significant vulnerabilities in BFSF, demonstrating how what was previously considered a robust defense against re-identification attacks can be systematically broken. The core of their discovery lies in the subtle ways linearity can emerge in seemingly non-linear cryptographic constructions under typical operating parameters, leading to unexpected information leakage.

The talk not only dissects the flaws in current PPRL practices but also proposes a novel, more resilient scheme dubbed SAUL (Solomon with Added Universal Linkage). SAUL aims to rectify the identified weaknesses by introducing a more robust non-linear component and a refined diffusion mechanism, thereby offering a stronger guarantee of privacy while maintaining practical utility. This work is highly significant for any organization handling sensitive, large-scale datasets—such as medical records or prison registries—where the need to link information across databases for research or public health purposes must be balanced with stringent privacy requirements. The findings challenge the security assumptions underpinning many current PPRL deployments and provide a clear path forward for building more secure systems.

The practical implications of this research are substantial. With real-world applications involving hundreds of millions of participants, such as cohort studies in Brazil, the security of PPRL schemes is not merely an academic concern but a critical foundation for protecting individual privacy on a massive scale. By demonstrating how a motivated adversary, even with an "honest but curious" posture, can re-identify individuals from encoded data, the authors underscore the urgent need for a paradigm shift in how these privacy-preserving techniques are designed and evaluated. SAUL represents a timely and well-reasoned response to this evolving threat landscape.

Background

▶ Watch: Introduction: Linking sensitive databases securely (0:00)

The fundamental problem addressed by this research is privacy-preserving record linkage (PPRL). Imagine two separate databases, say A and B, both containing sensitive personal identifiers (e.g., names, addresses, health IDs). A common task is to perform an inner join on these databases—that is, to identify individuals present in both—without revealing their plain text identities. This is crucial for applications like epidemiological studies, fraud detection, or cross-referencing criminal records, where the mere presence of an individual in a specific dataset (e.g., a prison record) is highly sensitive information.

Traditional approaches to this problem face significant hurdles. Directly using plain text identifiers is a clear privacy violation. While cryptographic hash functions could obscure identities, they are susceptible to errors like spelling mistakes or variations in data entry, making accurate linkage difficult. More advanced techniques like private computation (e.g., secure multi-party computation) offer strong privacy guarantees but are notoriously slow and computationally intensive, rendering them impractical for the massive datasets often encountered in real-world scenarios, such as Brazil's cohort study involving over 100 million participants.

Consequently, similarity-preserving encoding schemes emerged as a compromise. These methods transform plain text identifiers into encoded representations that retain enough similarity information to allow matching, even with minor discrepancies, while ideally obscuring the original data. Early iterations of these schemes, however, often maintained a near-perfect correlation between the similarity of plain text records and their encoded counterparts. This property, initially seen as desirable for linkage accuracy, proved to be a critical vulnerability. Attackers could construct a graph representing similarities in an auxiliary plain text database (e.g., a public phone book) and a similar graph from the encoded sensitive database. If the structures of these graphs were sufficiently isomorphic, an attacker could solve the graph isomorphism problem to link encoded records back to their plain text identities, effectively "breaking" the encoding.

In response to these graph isomorphism attacks, researchers developed improved schemes designed to introduce noise or obfuscation into the similarity scores. One notable approach was Differential Privacy Text and Match (DPMA), which aimed to provide only binary-like similarity information (ee.g., 0.5 for dissimilar records) to thwart graph isomorphism attacks. A key scheme in this evolution, and the primary target of the presented research, is Bloom filter similarity fusion (BFSF), first introduced at PETS in 2014. BFSF sought to hide the similarity of similar records by adding a "fusion layer" to standard Bloom filter constructions, making it a state-of-the-art method for PPRL. The attacker model for BFSF, and the context of this talk, assumes an honest but curious linkage unit—a server or entity that performs the matching, has access to the encoded database, and potentially an overlapping plain text database, and whose goal is to re-identify individuals.

Key Findings

▶ Watch: Bloom Filter Similarity Fusion (BFSF) scheme (3:30)

The central finding of this research is the successful breaking of Bloom filter similarity fusion (BFSF), a scheme previously considered secure against graph isomorphism attacks and a standard in privacy-preserving record linkage since its introduction at PETS 2014. The authors demonstrate that BFSF, despite its design to introduce non-linearity, harbors critical vulnerabilities that lead to information leakage and enable re-identification.

Specifically, the key discoveries are:

  1. Effective Linearity under Sparsity: While the Bloom filter creation process in BFSF involves non-linear OR operations, and the subsequent "fusion layer" uses XOR operations, the authors found that under typical parameter settings (e.g., Bloom filters of length 1,024 bits and records containing 20-30 bigrams), the intermediate Bloom filters become extremely sparse. In such sparse conditions, the OR operation behaves almost identically to an XOR operation. This effectively renders the entire BFSF encoding scheme, including its ostensibly non-linear components, linear.
  1. Two Forms of Information Leakage: This effective linearity leads to two critical forms of information leakage from the encoded data:
  • Plain Text XOR Approximation: The encoded representation of a record approximately corresponds to the bitwise XOR of its plain text components. This means an attacker can infer relationships between plain text records by observing their encoded XOR sum.
  • Plain Text String Length Correlation: The Hamming weight (number of set bits) of the encoded Bloom filter correlates with the length of the original plain text string. This leakage provides an additional side channel that an attacker can exploit to narrow down potential plain text matches.
  1. Homomorphism-Based Arithmetic Attack: The authors leveraged these two leakage properties to devise a novel attack called the homomorphism-based arithmetic attack. This attack involves searching for combinations of encoded records that sum (via XOR) to a zero vector, and then mapping these relationships back to the plain text domain. This represents a more sophisticated variant of previous graph isomorphism attacks, exploiting the underlying arithmetic properties revealed by the scheme's linearity.
  1. SAUL as a Robust Solution: To address these vulnerabilities, the research proposes a new scheme, SAUL (Solomon with Added Universal Linkage). SAUL fundamentally alters the Bloom filter construction process by replacing the vulnerable OR operations with a majority function. This change, combined with a repeated diffusion process, ensures that the scheme maintains strong non-linearity, preventing the information leakage observed in BFSF. SAUL demonstrates high linkage utility and minimal performance overhead, making it a practical and secure alternative for PPRL.

In essence, the key finding is a profound insight into the fragility of "security by obscurity" or "security by statistical diffusion" when underlying cryptographic primitives are not sufficiently robust across all operating conditions. The authors' work highlights that even seemingly minor design choices, like the choice between OR and XOR in specific contexts, can have catastrophic security consequences when combined with realistic data characteristics like sparsity.

Technical Deep Dive

▶ Watch: Identifying BFSF's linear fusion layer vulnerability (4:40)

The technical core of this research revolves around the detailed analysis of the Bloom filter similarity fusion (BFSF) scheme and the architectural improvements proposed in SAUL.

Dissecting Bloom Filter Similarity Fusion (BFSF)

BFSF, as presented at PETS 2014, was designed to provide privacy-preserving record linkage by encoding personal identifiers into Bloom filters and then applying a "fusion" layer to obscure direct similarities, thereby resisting graph isomorphism attacks. The process works in several stages:

  1. Bigram Generation and Hashing: For each plain text record (e.g., a name like "John Doe"), it is first broken down into a set of bigrams (overlapping pairs of characters, e.g., "Jo", "oh", "hn", "n ", " D", "Do", "oe"). Each bigram is then hashed multiple times (typically using k hash functions) to set k bits in an initially zeroed bit vector. This creates an "intermediate Bloom filter" for each individual bigram. The Hamming weight of this intermediate Bloom filter is equal to k.
  1. Record Bloom Filter Construction (OR Operation): All the intermediate Bloom filters corresponding to the bigrams of a single record are then combined. The standard BFSF scheme uses a bitwise OR operation across all these bigram Bloom filters to generate a single, comprehensive Bloom filter representing the entire record. For example, if a record has bigrams B1, B2, ..., Bn, its Bloom filter (BF_record) is BF_B1 OR BF_B2 OR ... OR BF_Bn.
  1. Fusion Layer (XOR Operation): This is the "similarity fusion" step. The final Bloom filter (BF_record) is then passed through a fusion layer. This layer takes groups of bits from BF_record and applies an XOR operation to them to produce the final encoded representation. The talk specifically mentions XORing "in this case three bits" of the previously calculated Bloom filter to produce each bit of the final "fusion" Bloom filter. The purpose of this layer is to destroy the direct correlation of similarities between plain text records and their encoded counterparts, particularly for dissimilar records, making graph isomorphism attacks difficult.

The Vulnerability: Effective Linearity

The authors identified a critical flaw in BFSF: while the fusion layer is explicitly linear (XOR), the Bloom filter creation step (ORing) appears non-linear. However, under typical parameter settings, this non-linearity breaks down:

  • Sparsity: Practical implementations of BFSF often use Bloom filters of a specific length, for example, 1,024 bits. A typical record might contain around 20 to 30 bigrams. Each bigram sets k bits (e.g., k=3 or k=4). This means that in an intermediate Bloom filter for a single bigram, only a very small fraction of bits are set to 1. Consequently, when multiple sparse bigram Bloom filters are combined using the OR operation, the resulting record Bloom filter also tends to be very sparse; most of its bits remain zero.
  • OR vs. XOR in Sparse Conditions: The crucial insight is that for two bits, the OR and XOR operations differ only when both bits are 1 (1 OR 1 = 1, but 1 XOR 1 = 0). When the Bloom filters are sparse, the probability of two or more bigram Bloom filters setting the exact same bit to 1 is incredibly low. As a result, the bitwise OR operation across many sparse vectors behaves almost identically to a bitwise XOR operation. If a bit is set to 1 by only one bigram, both OR and XOR will result in 1. If it's set by zero bigrams, both result in 0. Only if it's set by an even number of bigrams does XOR produce 0 where OR would produce 1. Given the sparsity, the probability of a bit being set by an even number of bigrams is significantly higher than by multiple bigrams.
  • Cascading Linearity: Since the initial OR operations effectively become linear (XOR), and the subsequent fusion layer is explicitly linear (XOR), the entire BFSF scheme collapses into an effectively linear transformation. The speaker notes that the probability of a bit being 1 being zero is incredibly high, thus making OR and XOR operations indistinguishable in practice.

The Homomorphism-Based Arithmetic Attack

This effective linearity leads to two critical information leakages:

  1. Plain Text XOR Leakage: The final encoded output approximates the XOR sum of the plain text bigrams. This means if an attacker has a candidate set of plain text records, they can predict the XOR sum of their encoded forms.
  2. Hamming Weight Leakage: The Hamming weight of the encoded Bloom filter (the number of set bits) directly correlates with the number of bigrams in the original plain text string. This provides an attacker with information about the length of the original identifier, which can be used to filter or rank potential matches.

The homomorphism-based arithmetic attack exploits these leaks. The attack searches for combinations of encoded records that, when XORed together, result in a zero vector. Because of the effective linearity, a zero vector in the encoded space implies a corresponding arithmetic relationship (likely an XOR sum resulting in zero) among the original plain text identifiers. An attacker with access to a plain text database (e.g., a phone book) can then find groups of plain text records that satisfy this same arithmetic property and map them to the observed encoded patterns. This is a powerful form of re-identification, a "slightly different form of the transmission attack than the one in the beginning" (referring to graph isomorphism). The authors demonstrated this attack on a "crafted dataset" to highlight its feasibility, arguing that the security of an encoding scheme "should not depend on the data you're encoding."

SAUL: The Proposed Solution

To counter these vulnerabilities, the authors propose SAUL (Solomon with Added Universal Linkage). SAUL's design focuses on re-introducing strong non-linearity and robust diffusion:

  1. Replacement of OR with Majority Function: The most significant change in SAUL is the replacement of the bitwise OR operation in the Bloom filter construction with a majority function. Instead of simply setting a bit to 1 if any bigram hashes to it, the majority function sets a bit to 1 only if the majority of the bigrams hash to that bit position. This significantly increases the non-linearity of the Bloom filter generation. The speaker refers to the poster session for a detailed argument on why the majority function is an excellent choice, but it effectively makes the scheme much harder to linearize.
  1. Repeated Diffusion (Confusion Trick): While the majority function initially creates a representation that is still "perfectly correlated between the plain text and encoded similarities" (meaning it would still be vulnerable to standard graph isomorphism attacks if used directly), SAUL applies the "confusion trick" (fusion layer) by repeating this process a couple of times. This implies multiple layers of the majority-based Bloom filter generation followed by a diffusion step, ensuring that the final encoding obscures direct similarity while maintaining sufficient information for linkage.

SAUL's Security and Utility

The authors presented evidence of SAUL's improved security and utility:

  • No Hamming Weight Correlation: SAUL exhibits no meaningful correlation between the Hamming weight of the encoding and the plain text string length. The speaker states, "We don't know anything about these plain texts," indicating that the leakage observed in BFSF is prevented.
  • Obscured Similarity Correlation: Similar to BFSF's original goal, SAUL ensures that only truly similar plain text records yield similar encoded data. Dissimilar records show no exploitable similarity correlation, effectively preventing standard graph isomorphism attacks.
  • Randomized Bigram Patterns: The probability that a bigram introduces a specific pattern is "close to 0.5," meaning no discernible patterns are leaked that could be used for other types of attacks.
  • High Linkage Quality: SAUL maintains a high linkage quality, meaning it is effective at correctly identifying matching records.
  • Efficient Performance: SAUL is computationally efficient, scaling linearly with the number of records. It takes approximately 14 seconds to compute and decode 100,000 records, which is only about 2 seconds slower than BFSF. This demonstrates that the enhanced security comes with only a "marginal" performance penalty, making SAUL practical for large-scale deployments.

Demo / Proof of Concept

▶ Watch: Introducing 'Solomon' as a new secure solution (8:00)

While the talk did not feature a live demonstration of the attack or the SAUL scheme in action, the authors presented experimental results validating their findings. They described running the "homomorphism-based arithmetic attack" on a crafted dataset. This dataset was specifically engineered to include the kinds of structural patterns that the attack is designed to find and exploit.

The use of a crafted dataset served to unequivocally demonstrate the vulnerability of BFSF under conditions that expose its effective linearity. The authors acknowledged that such a dataset "is not quite realistic," but critically argued that "the security of any encoding scheme should not depend on the data you're encoding." This highlights a fundamental principle: a secure scheme should be robust against a wide range of data characteristics, not just average or benign ones. The experiment successfully proved that the theoretical vulnerabilities identified in BFSF could be practically exploited to reveal sensitive information, underscoring the urgency of adopting more secure alternatives like SAUL.

Defensive Implications

▶ Watch: Solomon's security properties and practical utility (9:20)

The findings presented in this talk carry significant implications for organizations and practitioners involved in privacy-preserving record linkage (PPRL) and the broader field of privacy-enhancing technologies.

  1. Re-evaluate Existing BFSF Deployments: Any organization currently using Bloom filter similarity fusion (BFSF), or variations thereof, for PPRL should immediately re-evaluate the security posture of their systems. The core vulnerability—effective linearity under typical parameter settings (sparse Bloom filters)—means that these deployments are likely susceptible to the "homomorphism-based arithmetic attack" and other forms of re-identification, even if they were previously considered secure against graph isomorphism.
  1. Beyond Graph Isomorphism: Defenders must understand that the threat landscape for PPRL extends beyond traditional graph isomorphism attacks. The "homomorphism-based arithmetic attack" represents a new class of side-channel attacks that exploit subtle arithmetic properties and information leakage (e.g., plaintext XOR, Hamming weight correlation) that may not be apparent in a superficial security analysis.
  1. Prioritize Robust Non-Linearity: When designing or selecting PPRL schemes, a critical focus must be placed on ensuring strong and consistent non-linearity across all layers of the encoding process. As demonstrated, even seemingly non-linear operations like bitwise OR can become effectively linear under specific data conditions (like sparsity). Schemes must be rigorously tested under various parameter settings and data characteristics to prevent such breakdowns.
  1. Adopt SAUL or Similar Robust Alternatives: The proposed SAUL scheme offers a concrete, tested alternative that addresses the identified vulnerabilities without significant performance overhead. Organizations should consider adopting SAUL or other similarly designed schemes that incorporate robust non-linear functions (like the majority function) and multi-layered diffusion to enhance privacy guarantees.
  1. Security Independent of Data Characteristics: A key takeaway from the authors' argument about the "crafted dataset" is that the security of a PPRL scheme should not inherently depend on the statistical properties or density of the data it is encoding. Schemes must be designed to be robust even in edge cases or with highly sparse data, as these conditions can inadvertently expose weaknesses.
  1. Holistic Privacy Engineering: This research underscores the importance of a holistic approach to privacy engineering. Even seemingly minor design choices, or the interaction between cryptographic primitives and real-world data distributions, can have profound security implications. Continuous research, re-evaluation, and adoption of state-of-the-art secure methods are paramount for protecting sensitive information in large-scale data linkage scenarios.

Key Takeaways

  • Existing PPRL Schemes are Vulnerable: Widely used privacy-preserving record linkage (PPRL) schemes, particularly Bloom filter similarity fusion (BFSF) from PETS 2014, are not as secure as previously believed.
  • Effective Linearity is the Root Cause: Under typical sparse data conditions (e.g., 1,024-bit Bloom filters with 20-30 bigrams), BFSF's seemingly non-linear OR operations become effectively linear, rendering the entire scheme vulnerable.
  • New Attack Exploits Information Leakage: This linearity enables a "homomorphism-based arithmetic attack" that exploits two critical leaks: the encoded data approximates the XOR of plain text, and its Hamming weight correlates with plain text string length.
  • SAUL Offers a Robust Solution: The proposed SAUL scheme (Solomon with Added Universal Linkage) addresses these vulnerabilities by replacing the problematic OR operation with a majority function and employing repeated diffusion, ensuring strong non-linearity.
  • Improved Security with Minimal Performance Cost: SAUL provides significantly enhanced privacy guarantees without sacrificing utility or incurring a substantial performance penalty, making it a practical alternative for large-scale sensitive data linkage.
  • Security Must Not Depend on Data: The security of any PPRL scheme should be independent of the specific characteristics or sparsity of the data it processes; robust design is crucial for real-world deployments.

About the Speaker(s)

The talk was presented by a speaker who introduced himself as Robin from the University of Mannheim. The work is a joint effort with his supervisor, Professor Kamkhuis. The paper's authors are Frederik Armknecht and Jochen Schäfer, both affiliated with the University of Mannheim. Frederik Armknecht is likely the Professor Kamkhuis mentioned by the speaker, and Jochen Schäfer is a co-author. Their research focuses on cryptographic methods and privacy-enhancing technologies, particularly in the context of secure data processing and privacy-preserving record linkage. Their work contributes significantly to understanding the vulnerabilities in existing privacy schemes and developing more robust and practical solutions for sensitive data applications.

Reviews

Dr. Zero (Offensive Security Researcher) — STRONG ACCEPT

Breaking a decade-old privacy standard because the original designers didn't account for how data sparsity ruins non-linearity is exactly the kind of research we need. The authors proved that BFSF's core OR operations degrade into linear XORs under normal parameters, collapsing the whole scheme. SAUL is a clean, mathematically sound fix.

Heather Calloway (CISO) — MUST SEE

Researchers completely dismantled a decade-old standard for privacy-preserving data linkage, proving it systematically leaks plain text under normal operating conditions. If your organization links massive sensitive datasets across third parties relying on this scheme, your privacy guarantees are mathematically broken. This is mandatory viewing for your privacy engineering and data science leads.

→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026

All talks from Privacy Enhancing Technologies Symposium (PETS) 2026