Bloom Filter Encoding

A Bloom filter can definitively confirm an element is not in a set, but can only indicate an element may be present. This one-sided error property is fundamental to its design.

• False positives are possible and tunable
• False negatives are impossible by construction
• The probability of false positives grows with the number of inserted elements
• Typical configurations target a 0.1% to 1% false positive rate for PPRL applications

Each input string is processed through k independent hash functions, each mapping to a position in a fixed-size bit array. The corresponding bits are set to 1, creating a compact fingerprint.

• Common configurations use 15 to 30 hash functions
• Double hashing techniques simulate many hash functions from two base hashes
• The bit array length m and hash count k determine the false positive rate
• HMAC-SHA256 with per-application salts provides cryptographic strength

Bloom filters enable fuzzy matching of encoded strings through bit-level similarity metrics. The Dice coefficient or Jaccard similarity between two Bloom filters approximates the string similarity of the original plaintext.

• q-gram decomposition breaks names into overlapping character n-grams before encoding
• Bigrams (q=2) are standard for personal names like surnames
• Edit distance in plaintext correlates with bit disagreement in the filter
• Enables matching despite typographical errors without revealing the original string

Standard Bloom filters are vulnerable to frequency-based cryptanalysis where attackers exploit bit position frequencies to reconstruct plaintext. Hardened variants add multiple defensive layers.

• Secret salt per application prevents pre-computed rainbow table attacks
• Multiple hashing iterations increase computational cost for attackers
• Balancing ensures roughly equal numbers of 0s and 1s in the final filter
• XOR-folding with a random bit vector masks statistical patterns
• The Cryptographic Longterm Key (CLK) is a standardized hardened Bloom filter implementation

The dimensions of a Bloom filter directly impact privacy, accuracy, and performance. Larger filters provide better security but increase storage and comparison costs.

• Bit array length m: typically 500 to 1000 bits for PPRL
• Number of hash functions k: optimized as k = (m/n) * ln(2) where n is expected elements
• Sparse filters (fewer 1s) leak more information about individual q-grams
• Dense filters (more 1s) increase false positive rates but improve privacy
• Optimal configuration balances linkage quality against re-identification risk

Bloom filter encoding enables privacy-preserving record linkage by allowing parties to compare encoded identifiers without ever exchanging raw personal data. Only matching filter pairs reveal entity relationships.

• Each data custodian independently encodes their records with the same parameters
• Comparison occurs on the encoded representations only
• Non-matching records remain cryptographically opaque to all parties
• Supports both two-party and multi-party linkage protocols
• Compliant with GDPR and HIPAA data minimization principles

A hardened, salted hash-based encoding derived directly from Bloom filters. CLKs generate irreversible, length-preserving tokens from personal identifiers by incorporating a secret key into the hashing process. This prevents frequency-based cryptanalysis attacks that can compromise standard Bloom filters. CLKs are the de facto standard for encoding Q-grams of names and addresses in production PPRL systems.

The preprocessing step that splits strings into overlapping substrings of length Q before hashing into a Bloom filter. For example, 'SMITH' with Q=2 yields: S, SM, MI, IT, TH, H. This technique provides fuzzy matching capabilities because typographical errors only affect a subset of Q-grams, preserving partial similarity. Common values are bigrams (Q=2) and trigrams (Q=3).

The primary similarity metric used to compare two Bloom filters. It calculates the overlap of set bits: 2 × (|A ∩ B|) / (|A| + |B|). A threshold (typically 0.8–0.85) classifies pairs as matches. Unlike Jaccard similarity, the Dice coefficient is more sensitive to agreement in sparse bit arrays, making it ideal for the binary vectors produced by Bloom filter encoding.

A cryptographically enhanced Bloom filter that resists frequency-based attacks by incorporating a secret salt and multiple hashing iterations. Standard Bloom filters leak the relative frequency of Q-grams, enabling attackers to reconstruct plaintext via frequency analysis. Hardening adds a keyed-hash message authentication code (HMAC) layer, making the bit distribution uniform and the encoding provably irreversible.

A preprocessing step that partitions encoded datasets into mutually exclusive blocks to reduce the quadratic comparison cost. Locality-Sensitive Hashing (LSH) hashes similar Bloom filters into the same bucket with high probability, enabling blocking directly on encoded data without decryption. This reduces the comparison space from O(n²) to O(n·b) where b is the average block size.

The three critical parameters governing encoding quality: m (bit array length, typically 500 or 1000), k (number of hash functions, typically 15–30), and Q (Q-gram length). These control the trade-off between false positive rate and matching accuracy. Longer arrays reduce collisions but increase storage; more hash functions improve discrimination but increase computation. Optimal configuration depends on the expected dataset size and error tolerance.