Hardened Bloom Filter

The foundational probabilistic data structure that hardened Bloom filters extend. A standard Bloom filter encodes elements like Q-grams of a name into a bit array using k independent hash functions. It enables efficient set membership testing with a controllable false positive rate but is vulnerable to frequency-based cryptanalysis—an attacker can correlate bit positions to infer common Q-gram patterns. Hardened variants add secret salts and iterative hashing to defeat this attack vector.

The primary attack vector that hardened Bloom filters defend against. In standard Bloom filter encodings, the frequency of 1-bits at specific positions correlates directly with the frequency of the underlying Q-grams in the population. An attacker can:

• Bit position analysis: Identify which positions correspond to common bigrams like 'th' or 'an'
• Dictionary reconstruction: Map bit patterns back to likely plaintext values
• Re-identification: Match encoded records to known plaintext databases Hardening disrupts this by ensuring each record's bit positions are salted with a unique secret, making cross-record frequency analysis infeasible.

A cryptographic preprocessing step that partitions encoded datasets into mutually exclusive blocks to avoid the quadratic complexity of all-pairs comparison. Techniques include:

• Locality-Sensitive Hashing (LSH): Groups similar hardened Bloom filters into the same bucket with high probability
• Reference value encoding: Uses a set of public reference strings to create blocking keys
• Phonetic blocking: Groups records by Soundex or Double Metaphone encodings of encoded fields Private blocking must balance recall (not splitting true matches across blocks) against efficiency (minimizing unnecessary comparisons).

The broader cryptographic protocol framework in which hardened Bloom filters operate. In a three-party honest-but-curious model:

• Data custodians: Encode their records using hardened Bloom filters with their own secret keys
• Linkage unit: Receives only the encoded filters, never the plaintext or secret keys
• Comparison: Computes similarity metrics like Dice coefficient directly on the encoded bit arrays
• Result delivery: Returns only matching record pairs above a threshold to the custodians This architecture ensures that even the party performing the linkage learns nothing about non-matching records.

The primary similarity metric computed on hardened Bloom filter bit arrays during private comparison. Defined as:

• Formula: 2 × |A ∩ B| / (|A| + |B|)
• Range: 0.0 (no overlap) to 1.0 (identical bit patterns)
• Thresholding: Pairs exceeding a calibrated threshold (typically 0.7–0.85) are classified as matches Unlike Jaccard similarity, Dice gives double weight to agreements, making it more robust to the sparsity patterns introduced by cryptographic hardening. The choice of threshold directly controls the precision-recall tradeoff.