Fuzzy PSI

Fuzzy PSI replaces exact equality checks with distance metrics such as Hamming distance, edit distance, or cosine similarity. Instead of testing x == y, the protocol evaluates distance(x, y) ≤ threshold. Common techniques include:

• Locality-sensitive hashing (LSH) to map similar items to the same hash bucket with high probability
• Threshold homomorphic encryption to compute encrypted distances without revealing raw values
• Garbled circuit evaluation of the distance function and comparison logic This allows matching of names with typos, addresses with formatting variations, or biometric templates with natural intra-user variance.

Fuzzy PSI is critical for privacy-preserving biometric identification. A user's biometric template (e.g., fingerprint minutiae, face embedding, iris code) is matched against a database without revealing the template to the server or the database entries to the client.

• The protocol outputs only the identifiers of templates within a similarity threshold
• Prevents biometric data leakage even if the server is compromised
• Enables applications like private watchlist screening and secure authentication Real-world systems often combine fuzzy PSI with secure enclaves or homomorphic encryption to protect templates during the matching computation itself.

Fuzzy PSI handles typographical errors, transliteration variants, and formatting inconsistencies in personal data. Use cases include:

• Contact discovery that matches names despite minor misspellings
• Private record linkage across healthcare databases with inconsistent patient name entries
• Sanctions screening that catches alias variations and deliberate misspellings Protocols often encode strings into Bloom filters of n-grams or use Soundex/Metaphone phonetic encodings as a pre-processing step before applying cryptographic matching, reducing the problem to a set intersection over encoded representations.

Several protocol variants define different output behaviors for fuzzy matching:

• Threshold PSI: Reveals all server elements within a specified distance of any client element
• Threshold PSI with payload: Returns associated metadata (labels) for matched elements
• Fuzzy PSI cardinality: Reveals only the count of approximate matches, not the elements themselves
• Outsourced fuzzy PSI: Delegates the heavy cryptographic computation to two non-colluding servers Each variant trades off information leakage against functionality, allowing system designers to select the minimal disclosure required for their application.

A core building block for efficient fuzzy PSI is the ability to hash items such that similar inputs produce similar hashes while preserving cryptographic privacy. Key techniques:

• Locality-sensitive hashing (LSH) families like MinHash for Jaccard similarity and SimHash for cosine distance
• Secure LSH where hash parameters are secret-shared or generated via oblivious PRF to prevent leakage
• Embedding techniques that map structured data (graphs, sequences) into fixed-length vectors suitable for LSH These hashing schemes reduce the fuzzy matching problem to a standard PSI over hash buckets, dramatically improving computational efficiency.

Fuzzy PSI protocols operate under different security guarantees:

• Semi-honest security: Parties follow the protocol but may attempt to learn from the transcript. The protocol reveals the approximate matches and the distance threshold
• Malicious security: Protects against arbitrary deviations, preventing an adversary from learning non-matching elements by manipulating distance computations
• Leakage considerations: Beyond the intersection, fuzzy PSI may leak the distance distribution or the number of near-matches. Advanced protocols minimize this through differential privacy noise addition or secure comparison circuits that reveal only binary match/no-match results.

A hashing technique that maximizes collisions for similar inputs rather than identical ones. LSH functions map items that are close under a distance metric (e.g., Hamming, Euclidean, Jaccard) to the same bucket with high probability.

• Core property: Pr[h(x) = h(y)] is high when dist(x,y) is small
• Common families: MinHash for Jaccard similarity, SimHash for cosine distance, random projections for Euclidean distance
• Role in Fuzzy PSI: Transforms the approximate matching problem into an exact matching problem over hash buckets, allowing standard PSI protocols to operate on the LSH outputs
• Tuning trade-off: More hash tables increase recall but also increase communication and false positives

Fuzzy PSI protocols must define a concrete similarity threshold to determine what constitutes a match. The choice of distance metric fundamentally shapes the protocol design.

• Levenshtein distance: Minimum number of single-character insertions, deletions, and substitutions
• Damerau-Levenshtein: Extends Levenshtein to include transpositions of adjacent characters
• Jaro-Winkler: Weighted metric optimized for short strings like names, giving higher scores to strings that match from the beginning
• Hamming distance: Number of differing positions between two equal-length strings, commonly used for biometric templates and error-correcting codes
• Threshold selection: Must balance false positives (privacy leakage) against false negatives (missed matches)

A generic approach that evaluates the distance computation and threshold comparison inside a secure two-party computation protocol, typically using garbled circuits.

• Workflow: Alice and Bob secret-share their inputs, then jointly evaluate a Boolean circuit that computes dist(x,y) < threshold for each candidate pair
• Circuit components: XOR gates for Hamming distance, or more complex edit distance dynamic programming circuits
• Optimization: Use free-XOR and half-gate techniques to minimize garbled circuit size
• Limitation: Circuit size scales with string length and alphabet size, making this approach expensive for long strings or large sets
• Advantage: Provides malicious security and works with arbitrary distance functions expressible as circuits

Transforms input strings into fixed-length vectors in a metric space where distance correlates with semantic or syntactic similarity, then applies secure vector comparison.

• Neural embeddings: Use pre-trained models like FastText or sentence transformers to map strings to dense vectors where cosine similarity reflects real-world similarity
• Quantization: Discretize embedding dimensions to enable efficient secure comparison via garbled circuits or homomorphic encryption
• Threshold inner-product PSI: A specialized protocol that reveals only whether the inner product of two vectors exceeds a threshold
• Advantage over LSH: Captures semantic similarity (e.g., 'NYC' ≈ 'New York') that character-level metrics miss
• Privacy consideration: Embedding model must not leak information about the training data distribution

Leverages error-correcting codes to tolerate differences between biometric templates or noisy measurements while maintaining cryptographic binding.

• Fuzzy commitment: Encode a secret key using an ECC, then XOR with a biometric template. Decoding succeeds only if a fresh reading is within the error-correction radius
• Reed-Solomon codes: Popular choice for fuzzy vaults due to efficient decoding of burst errors
• Fuzzy extractors: Generate a stable cryptographic key from noisy biometric data, producing both a public helper string and a uniformly random key
• Application: Biometric-based private set intersection where fingerprints or face embeddings are matched without revealing raw templates
• Security bound: The entropy loss from the helper string must be quantified to ensure the extracted key remains strong

Fuzzy PSI often reveals only aggregate information rather than the exact matching elements, providing stronger privacy guarantees for sensitive applications.

• Fuzzy PSI cardinality: Only the count of approximate matches is revealed, not which elements matched
• Threshold fuzzy PSI: Reveals the intersection only if the number of matches exceeds a minimum threshold, preventing inference about small intersections
• Fuzzy PSI-sum: Associates values with set elements and reveals the sum of values for approximately matching pairs
• Application: Two hospitals discover how many patients they have in common (with name typos tolerated) without revealing which patients overlap
• Efficiency gain: Cardinality-only protocols can use randomized response and differential privacy to further reduce communication