Private and Secure Fuzzy Name Matching.

Harsh Kasyap, Ugur-Ilker Atmaca, Carsten Maple, Graham Cormode, Jiancong HearXiv 2024 · OpenReview

Abstract

Financial institutions are increasingly required to share intelligence to combat money laundering and fraud, yet they are simultaneously constrained by stringent data privacy regulations like GDPR. This paper introduces a novel, efficient scheme for "fuzzy" name matching that allows institutions to identify potential matches in encrypted datasets. By integrating MinHash signatures with CKKS Fully Homomorphic Encryption (FHE) and a specialized clustering mechanism, the authors demonstrate a system that reduces communication overhead by 30–300x while maintaining near-perfect precision.

Introduction

The primary challenge in financial intelligence sharing is the "catch-22" of privacy versus utility. While sharing customer lists is essential for identifying bad actors, raw data sharing is often legally prohibited. Furthermore, names are rarely consistent across different databases due to typos, nicknames, or varying formats (e.g., "Jon Doe" vs. "Jonathan P. Doe"). Traditional Private Set Intersection (PSI) methods typically require exact matches and fail to handle this "fuzziness." Existing fuzzy solutions often rely on Secure Multi-Party Computation (SMPC), which is frequently too slow or communication-intensive for large-scale industrial use.

System Architecture

The proposed system facilitates a secure interaction between a Querier (Organisation A) and a Responder (Organisation B). The workflow is designed to ensure that the Querier only learns if a match exists above a certain threshold, while the Responder learns nothing about the query itself.

Overview of the privacy-preserving fuzzy name matching workflow between the Querier (Organisation A) and the Responder (Organisation B).

Methodology

The architecture relies on four key technological pillars:

  1. MinHash Signatures: To handle fuzziness, names are decomposed into n-gram "shingles" and converted into compact MinHash signatures. This allows for the estimation of Jaccard similarity without exhaustive character-by-character comparison.
  2. CKKS Homomorphic Encryption: Signatures are encrypted using the CKKS scheme, which supports approximate arithmetic on encrypted real numbers. This enables the calculation of cosine similarity directly on encrypted data.
  3. Clustering-based Matching: To avoid the computational cost of comparing a query against every record in a massive database, the responder pre-clusters their data using K-Means. Encrypted queries are first compared against cluster centroids, significantly pruning the search space.
  4. Privacy Safeguards: The protocol is structured so that the Querier receives only the final "Catch/No-Catch" result based on a threshold, preventing the leakage of similarity scores or other metadata.

Experimental Evaluation

The researchers validated the system using three datasets:

  • North Carolina Voter Registration (NCVR): A benchmark for record linkage.
  • Library Catalogue Datasets: Used to test the system's robustness against longer "names" (book titles).
  • US Census Data: Synthetic data used to measure performance against controlled Levenshtein distances (typos).

Key Results

The system demonstrates significant improvements over existing methods:

  • Efficiency: Communication costs were reduced from a theoretical 314GB for serial searches to just 1–2GB. Matching 20,000 records took only 0.45 hours, compared to 1.8 hours using standard additive homomorphic encryption (AHE).
  • Scalability: The clustering mechanism allowed the system to scale to 1 million records with a manageable memory footprint of approximately 77GB.
  • Accuracy: The system achieved 99.5% precision at specific thresholds. It maintained nearly 100% precision and recall for names with a single typo (Levenshtein Distance of 1).
  • Throughput: A search of 1,000 names against a 100,000-record database was completed in approximately 1,000 seconds, meeting practical operational requirements.

Conclusion and Future Work

This research provides a scalable and privacy-preserving solution for fuzzy name matching in the financial sector. While the clustering mechanism introduces a slight trade-off in recall—occasionally missing matches if a name is misclustered—the performance gains make it a viable tool for real-world applications. Future research will focus on improving recall within the clustering framework and enhancing security against malicious actors beyond the current "honest-but-curious" model.

Summary updated

BibTeX
@misc{kasyap2024private,
  author = {Harsh Kasyap and Ugur-Ilker Atmaca and Carsten Maple and Graham Cormode and Jiancong He},
  title = {{Private and Secure Fuzzy Name Matching.}},
  year = {2024},
  url = {https://openreview.net/forum?id=XbJW6phvo9},
}
Figure