privacy-record-linkage

name	privacy-record-linkage
description	Implement privacy-preserving record linkage across datasets using Bloom filter encoding, secure hash matching, threshold tuning for precision and recall, and false positive management. Enables entity resolution without exposing raw personally identifiable information between parties.
license	Apache-2.0
metadata	{"author":"mukul975","version":"1.0","domain":"privacy","subdomain":"privacy-engineering","tags":"record-linkage, bloom-filters, entity-resolution, secure-matching, pprl"}

Privacy-Preserving Record Linkage

Overview

Privacy-Preserving Record Linkage (PPRL) enables two or more organizations to identify matching records across their datasets without revealing the underlying personal data to each other. This is critical for healthcare research, fraud detection, national statistics, and cross-organizational analytics where direct data sharing is prohibited by privacy regulations.

Approach Comparison

Approach	Privacy Level	Accuracy	Scalability	Communication Cost
Bloom Filter Encoding	High	Good (>95% F1)	Very High	Low
Secure Hash Matching	Very High	High (exact match only)	Very High	Very Low
Secure Multi-Party Computation	Cryptographic	Very High	Medium	High
Trusted Third Party	Depends on TTP	Very High	High	Medium
Differential Privacy Linkage	Formally private	Moderate	High	Low

Bloom Filter-Based PPRL

How It Works

1. Each organization encodes their quasi-identifiers (name, date of birth, address) into Bloom filters
2. The Bloom filter encoding uses cryptographic hash functions with a shared secret key
3. Encoded Bloom filters are compared using similarity metrics (Dice coefficient, Jaccard)
4. Matching pairs above a threshold are identified as linked records
5. Raw data is never exchanged — only Bloom filter bit arrays

Bloom Filter Encoding Implementation

"""
Privacy-preserving record linkage using Bloom filter encoding.
Implements the approach described by Schnell, Bachteler, and Reiher (2009).
"""

import hashlib
import hmac
import math
from typing import Optional
import numpy as np


class BloomFilterEncoder:
    """
    Encode string attributes into Bloom filters for privacy-preserving
    record linkage using cryptographic keyed hashing.
    """

    def __init__(
        self,
        filter_size: int = 1024,
        num_hash_functions: int = 30,
        ngram_size: int = 2,
        secret_key: bytes = b""
    ):
        """
        Args:
            filter_size: Number of bits in the Bloom filter
            num_hash_functions: Number of hash functions (k)
            ngram_size: Size of character n-grams (bigrams = 2)
            secret_key: Shared secret key for HMAC hashing
        """
        self.filter_size = filter_size
        self.num_hash_functions = num_hash_functions
        self.ngram_size = ngram_size
        self.secret_key = secret_key

    def _generate_ngrams(self, value: str) -> list[str]:
        """Generate character n-grams from a string value."""
        # Pad the string to handle edge characters
        padded = f"_{value}_"
        return [
            padded[i:i + .ngram_size]
             i  ((padded) - .ngram_size + )
        ]

     () -> :
        
        message = .encode()
        digest = hmac.new(.secret_key, message, hashlib.sha256).digest()
        
        position = .from_bytes(digest[:], byteorder=) % .filter_size
         position

     () -> np.ndarray:
        
        bloom_filter = np.zeros(.filter_size, dtype=np.uint8)

        
        normalized = value.strip().lower()

        
        ngrams = ._generate_ngrams(normalized)

        
         ngram  ngrams:
             h  (.num_hash_functions):
                position = ._hash_ngram(ngram, h)
                bloom_filter[position] = 

         bloom_filter

     () -> np.ndarray:
        
        composite = np.zeros(.filter_size, dtype=np.uint8)

         attr_name, attr_value  attributes.items():
             attr_value:
                
                salted_key = .secret_key + attr_name.encode()
                encoder = BloomFilterEncoder(
                    filter_size=.filter_size,
                    num_hash_functions=.num_hash_functions,
                    ngram_size=.ngram_size,
                    secret_key=salted_key
                )
                attr_bf = encoder.encode_value(attr_value)
                composite = np.bitwise_or(composite, attr_bf)

         composite


 :
    


     () -> :
        
        intersection = np.(np.bitwise_and(bf1, bf2))
        cardinality_sum = np.(bf1) + np.(bf2)

         cardinality_sum == :
             

          * intersection / cardinality_sum


     () -> :
        
        intersection = np.(np.bitwise_and(bf1, bf2))
        union = np.(np.bitwise_or(bf1, bf2))

         union == :
             

         intersection / union

     () -> [[, , ]]:
        
        metric_fn = (
            .dice_coefficient  similarity_metric == 
             .jaccard_similarity
        )

        matches = []

         id_a, bf_a  encodings_a:
            best_score = 
            best_id_b = 

             id_b, bf_b  encodings_b:
                score = metric_fn(bf_a, bf_b)
                 score > best_score:
                    best_score = score
                    best_id_b = id_b

             best_score >= threshold  best_id_b   :
                matches.append((id_a, best_id_b, best_score))

         matches

Secure Hash Matching

For exact matching scenarios where approximate matching is not needed.

"""
Secure hash-based record linkage for exact matching.
Uses keyed HMAC to prevent rainbow table attacks.
"""

import hashlib
import hmac


class SecureHashLinker:
    """
    Link records across organizations using keyed hash matching.
    Suitable for exact match on standardized identifiers.
    """

    def __init__(self, shared_key: bytes):
        self.shared_key = shared_key

    def hash_identifier(self, *fields: str) -> str:
        """
        Create a keyed hash of concatenated identifier fields.

        Args:
            fields: Identifier fields in standardized order
                    e.g., ("john", "smith", "19900115")

        Returns:
            Hex-encoded HMAC-SHA256 hash
        """
        # Normalize and concatenate fields
        normalized = "|".join(f.strip().lower() for f in fields)

        # Generate keyed hash
        digest = hmac.new(
            self.shared_key,
            normalized.encode("utf-8"),
            hashlib.sha256
        ).hexdigest()

        return digest

    def hash_dataset(
        self,
        records: list[dict],
        id_field: str,
        linkage_fields: list[str]
    ) -> dict[str, str]:
        """
        Hash all records in a dataset for linkage.

        Returns mapping of hash -> record_id.
        """
        hash_map = {}

        for record  records:
            fields = [(record.get(f, ))  f  linkage_fields]
            record_hash = .hash_identifier(*fields)
            hash_map[record_hash] = record[id_field]

         hash_map


     () -> [[, ]]:
        
        common_hashes = (hashes_a.keys()) & (hashes_b.keys())
         [(hashes_a[h], hashes_b[h])  h  common_hashes]

Threshold Tuning

Methodology

Threshold Range	Precision	Recall	Use Case
0.90 - 1.00	Very High	Low	High-stakes decisions (medical records)
0.80 - 0.90	High	Medium	Standard record linkage
0.70 - 0.80	Medium	High	Exploratory analysis, broad matching
0.60 - 0.70	Low	Very High	Candidate generation (with manual review)

Optimal Threshold Selection Process

1. Generate labeled pairs: Create a sample of known matches and non-matches
2. Compute similarity scores: Calculate Dice/Jaccard for all pairs in the sample
3. Plot precision-recall curve: Sweep threshold from 0 to 1
4. Select threshold: Choose based on acceptable false positive rate for the use case
5. Validate: Test on held-out labeled data

False Positive Management

"""
Post-linkage false positive reduction through multi-stage verification.
"""


class FalsePositiveManager:
    """
    Reduce false positive matches through additional verification stages
    without revealing raw data between parties.
    """

    def __init__(self, primary_threshold: float = 0.8, verification_threshold: float = 0.9):
        self.primary_threshold = primary_threshold
        self.verification_threshold = verification_threshold

    def multi_field_verification(
        self,
        candidate_pairs: list[tuple[str, str, float]],
        secondary_encodings_a: dict[str, dict[str, np.ndarray]],
        secondary_encodings_b: dict[str, dict[str, np.ndarray]],
        matcher: BloomFilterMatcher
    ) -> list[tuple[str, str, float, bool]]:
        """
        Verify candidate matches using additional encoded fields.

        Args:
            candidate_pairs: (id_a, id_b, primary_score) from initial matching
            secondary_encodings_a: {record_id: {field: bloom_filter}} from org A
            secondary_encodings_b: {record_id: {field: bloom_filter}} from org B

        Returns:
            (id_a, id_b, composite_score, verified) for each candidate
        """
        verified_pairs = []

        for id_a, id_b, primary_score in candidate_pairs:
            secondary_scores = []

            fields_a = secondary_encodings_a.get(id_a, {})
            fields_b = secondary_encodings_b.get(id_b, {})

            common_fields = (fields_a.keys()) & (fields_b.keys())

             field_name  common_fields:
                score = matcher.dice_coefficient(
                    fields_a[field_name],
                    fields_b[field_name]
                )
                secondary_scores.append(score)

             secondary_scores:
                avg_secondary = (secondary_scores) / (secondary_scores)
                composite =  * primary_score +  * avg_secondary
                verified = composite >= .verification_threshold
            :
                composite = primary_score
                verified = primary_score >= .verification_threshold

            verified_pairs.append((id_a, id_b, composite, verified))

         verified_pairs

Security Considerations

Attack	Description	Mitigation
Frequency analysis	Analyzing bit patterns to infer common values	Use composite Bloom filters (CLK), add noise bits
Dictionary attack	Pre-computing Bloom filters for known values	Use strong shared secret keys, rotate keys periodically
Bit pattern cryptanalysis	Exploiting structure in Bloom filter bit patterns	Sufficient filter size (>= 1024), adequate hash functions (>= 20)
Collision exploitation	Deliberately crafting records to match target hashes	HMAC-based hashing, input validation

References

• Schnell, R., Bachteler, T., and Reiher, J. "Privacy-Preserving Record Linkage Using Bloom Filters." BMC Medical Informatics and Decision Making, 9(1):41, 2009.
• Vatsalan, D., Christen, P., and Verykios, V.S. "A Taxonomy of Privacy-Preserving Record Linkage Techniques." Information Systems, 38(6):946-969, 2013.
• Randall, S.M. et al. "Privacy-Preserving Record Linkage on Large Real World Datasets." Journal of Biomedical Informatics, 50:205-212, 2014.
• AIHW (Australian Institute of Health and Welfare) PPRL Implementation Guide
• Christen, P. "Data Matching: Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection." Springer, 2012.