Cryptographic Longterm Key (CLK)

CLK encoding builds upon standard Bloom filters but adds critical cryptographic hardening to resist frequency-based attacks. The process involves:

• Multiple hash functions mapping n-grams to bit positions
• A secret salt unique to each data custodian
• Iterative hashing (typically HMAC-SHA256) to slow brute-force attacks
• Length-preserving output that maintains a fixed bit-array size regardless of input length

This hardening ensures that identical plaintext values encoded with different salts produce entirely different bit patterns, preventing cross-database frequency analysis.

CLK encoding begins by decomposing identifier strings into overlapping character n-grams, typically bigrams or trigrams. For example, the name 'JON' yields bigrams: JO, ON. This tokenization provides inherent fuzzy matching capability because:

• Typographical errors affect only a subset of n-grams
• Transpositions like 'JOHN' vs 'JONH' still share common bigrams
• Phonetic variations preserve partial n-gram overlap

The choice of n-gram size represents a critical trade-off between match recall (smaller n-grams) and resistance to false positives (larger n-grams).

The CLK encoding function is cryptographically one-way, meaning the original plaintext cannot be recovered from the encoded bit-array. This property is achieved through:

• Hash-based bit setting rather than reversible mapping
• Collision tolerance where multiple n-grams may set the same bit
• Lossy compression inherent to Bloom filter structures
• No decryption key exists in the system architecture

This irreversibility satisfies regulatory requirements under GDPR and HIPAA for pseudonymization, as the CLK alone cannot re-identify individuals without access to the original plaintext.

Despite cryptographic hardening, CLKs preserve the ability to compute approximate string similarity through set-based distance metrics on the encoded bit-arrays. Common comparison methods include:

• Dice coefficient: 2 * |A ∩ B| / (|A| + |B|) measuring bit overlap
• Jaccard similarity: |A ∩ B| / |A ∪ B| for set-based comparison
• Hamming distance: counting differing bit positions

These metrics enable fuzzy matching with edit distance thresholds, allowing 'JON' and 'JOHN' to produce a high similarity score while 'JON' and 'MARY' score near zero, all without decrypting the underlying identifiers.

Standard Bloom filter encodings are vulnerable to frequency-based attacks where an adversary exploits the fact that common names produce consistent bit patterns. CLK encoding counters this through:

• Per-database salting that randomizes bit positions across custodians
• Bloom filter parameter tuning to control the false positive rate
• Balanced bit density preventing frequency signature leakage
• Optional noise injection adding random bits to mask true patterns

These defenses ensure that even if an attacker obtains multiple CLK databases, they cannot correlate records by frequency analysis of the encoded bit patterns.

Production CLK implementations require careful parameter selection to balance privacy guarantees against linkage accuracy. Key configuration decisions include:

• Bloom filter length: typically 500-1000 bits for personal identifiers
• Number of hash functions: 15-30 for optimal bit distribution
• N-gram size: bigrams for short names, trigrams for longer fields
• HMAC iterations: 1000+ rounds to impose computational cost on attackers
• Salt entropy: 256-bit random values generated per deployment

These parameters directly impact the false match rate and false non-match rate of the overall linkage pipeline.

A cryptographically enhanced Bloom filter that incorporates a secret key and multiple HMAC-based hashing iterations to resist frequency-based cryptanalysis attacks. Key properties include:

• Length-preserving: Output size is fixed regardless of input length
• Irreversible: Cannot recover plaintext from the bit-array
• Salted: Unique per-participant keys prevent cross-database linkage
• Collision-resistant: Multiple hash iterations obscure bit patterns

A cryptographic preprocessing step that partitions encoded datasets into mutually exclusive blocks to reduce the quadratic computational complexity of record linkage. Techniques include Locality-Sensitive Hashing (LSH) and reference value encoding. Without blocking, comparing every record pair across two databases of 1 million records each would require 10^12 comparisons—blocking reduces this to manageable subsets without leaking plaintext similarity.

The foundational statistical framework for probabilistic record linkage that computes match weights based on agreement and disagreement patterns across record fields. The model calculates:

• M-probability: Likelihood that matching records agree on a field
• U-probability: Likelihood that non-matching records agree by chance
• Composite weight: Sum of log-likelihood ratios across all fields Pairs exceeding an upper threshold are classified as matches; those below a lower threshold as non-matches; the remainder require clerical review.

An algorithmic technique that hashes similar input items into the same buckets with high probability, used extensively in private blocking for PPRL. MinHash is a popular LSH family that estimates Jaccard similarity between sets by comparing minimum hash values. LSH enables efficient approximate nearest-neighbor search on encoded records, dramatically reducing the candidate pair space while maintaining high recall for true matches.

A PPRL protocol where three or more data custodians jointly compute matching records without revealing their full datasets to any central third party. Each party encrypts their identifiers using a shared CLK scheme with unique per-party salts. The protocol uses Private Set Intersection Cardinality (PSI-CA) and secure comparison protocols to identify matches across all parties while ensuring that only the intersection is revealed.