Glossary

Secure Edit Distance

A secure multi-party computation protocol that allows two parties to compute the string edit distance between their private inputs without revealing the underlying strings to each other.

Get in touch Learn more

Developer demonstrating multi-agent tool use, agent tool selection interface on laptop, casual tech demo moment.

CRYPTOGRAPHIC STRING COMPARISON

What is Secure Edit Distance?

A secure multi-party computation protocol enabling two parties to compute the edit distance between their private strings without revealing the strings themselves.

Secure edit distance is a cryptographic protocol that allows two parties to jointly compute the Levenshtein distance—the minimum number of insertions, deletions, or substitutions required to transform one string into another—between their respective private inputs without disclosing the underlying strings to each other or any third party. It extends standard fuzzy string matching into the domain of secure multi-party computation (SMPC).

The protocol typically leverages garbled circuits or homomorphic encryption to evaluate a dynamic programming matrix over encrypted data, ensuring that only the final integer distance value is revealed. This primitive is foundational to privacy-preserving record linkage (PPRL), enabling entities to identify matching records across databases based on approximate name or address similarity while maintaining strict cryptographic guarantees against data leakage.

CRYPTOGRAPHIC GUARANTEES

Key Properties of Secure Edit Distance

Secure Edit Distance protocols transform a classic dynamic programming algorithm into a privacy-preserving computation, ensuring two parties learn only the similarity score and nothing else about each other's private strings.

Garbled Circuit Evaluation

The most common realization of secure edit distance uses Yao's Garbled Circuits, where the edit distance algorithm is compiled into a Boolean circuit. One party acts as the garbler who encrypts the circuit, and the other acts as the evaluator who computes the output obliviously using Oblivious Transfer for input wire labels.

The circuit computes the full Wagner-Fischer dynamic programming table
Each cell requires a MIN gate over three inputs: substitution, insertion, and deletion costs
Circuit size is O(n × m) where n and m are the string lengths
Optimized circuits use free-XOR and half-gate techniques to reduce overhead

O(n × m)

Circuit Complexity

Input Privacy Guarantee

The protocol provides computational privacy against semi-honest adversaries: neither party can learn the other's input string beyond what is inferable from the final edit distance and their own input. The security proof reduces to the Decisional Diffie-Hellman assumption or symmetric cryptographic primitives depending on the instantiation.

No intermediate DP table values are revealed to either party
The oblivious transfer step hides which wire labels are selected
Output is revealed only to the designated recipient, not both parties by default
Does not hide the string lengths unless padding to a fixed maximum is applied

Semi-Honest

Adversary Model

Levenshtein Distance Variant

The standard secure edit distance implements Levenshtein distance with unit costs for insertion, deletion, and substitution. The underlying DP recurrence is:

d[i][j] = min( d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + cost )

Substitution cost is 0 if characters match, 1 otherwise
Damerau-Levenshtein (adding transposition) requires a more complex circuit with additional state
Custom cost matrices for Needleman-Wunsch alignment can be embedded as lookup tables in the circuit
The output is a single integer representing the minimum number of edits

Unit Cost

Default Metric

Threshold Optimization

For record linkage applications, computing the full edit distance is often unnecessary—only whether the distance falls below a threshold k matters. This enables significant circuit optimization:

The DP table can be banded to width 2k+1 around the diagonal
Circuit complexity reduces from O(n × m) to O(k × min(n, m))
Early termination logic can be embedded to abort computation once the minimum exceeds k
Typical thresholds for name matching range from k=1 to k=3

O(k × n)

Optimized Complexity

Homomorphic Encryption Alternative

While garbled circuits dominate, secure edit distance can also be implemented using Fully Homomorphic Encryption (FHE) or Somewhat Homomorphic Encryption (SHE). In this model, one party encrypts their string and sends it to the other, who homomorphically evaluates the DP matrix.

Eliminates the constant-round communication pattern of garbled circuits
Suffers from higher computational overhead due to ciphertext operations
Well-suited for asymmetric settings where one party has more compute
The TFHE and CKKS schemes support the required comparison and addition operations

Non-Interactive

Communication Pattern

Application in PPRL Pipelines

Secure edit distance serves as the private comparison function within larger Privacy-Preserving Record Linkage workflows. After a private blocking step reduces the candidate pair space, secure edit distance is evaluated on each candidate pair to produce a similarity score.

Pairs with distance below a threshold proceed to further linkage steps
Often combined with Bloom filter encodings for the blocking phase
The output score feeds into the Felligi-Sunter probabilistic matching model
Enables fuzzy matching on encrypted identifiers like names and addresses without exposing plaintext

Fuzzy

Matching Type

SECURE EDIT DISTANCE

Frequently Asked Questions

Clear answers to common questions about the cryptographic protocols that compute string similarity without revealing the underlying private data.

Secure edit distance is a cryptographic protocol that allows two parties, each holding a private string, to jointly compute the edit distance between their strings without revealing the strings themselves to each other. The protocol leverages secure multi-party computation (SMPC) techniques, most commonly a garbled circuit implementation of the Wagner-Fischer dynamic programming algorithm. The parties first secret-share their inputs, then evaluate a boolean circuit that computes the minimum number of insertions, deletions, and substitutions required to transform one string into the other. The output—the edit distance value—is revealed to one or both parties, but no intermediate state or character-level information is leaked. This enables privacy-preserving fuzzy matching in applications like genomic sequence alignment and private record linkage.

SECURE EDIT DISTANCE

Real-World Applications

Secure edit distance protocols enable privacy-preserving fuzzy matching across domains where data sensitivity is paramount, from healthcare to national security.

Patient Record Deduplication

Hospitals and health information exchanges use secure edit distance to merge duplicate patient records across institutions without exposing protected health information (PHI).

Two hospitals compute the similarity of names like "Jon Smith" and "John Smyth" without revealing the plaintext strings
Enables HIPAA-compliant master patient index creation
Reduces medical errors caused by fragmented records while maintaining strict privacy guarantees

Cross-Border Financial Sanctions Screening

Financial institutions leverage secure edit distance to screen transactions against sanctions lists without exposing their customer databases to foreign regulators.

Banks in different jurisdictions compute name similarity against OFAC and UN blacklists
Handles transliteration variants of Arabic, Cyrillic, and Mandarin names
Prevents money laundering while preserving banking secrecy laws

National Security Watchlist Matching

Intelligence agencies use secure edit distance to cross-reference watchlists across allied nations without revealing sensitive source identities.

Computes fuzzy matches on aliases and transliterated names
Protects classified sources and methods during collaborative screening
Enables Five Eyes interoperability without raw data sharing

Genomic Sequence Alignment

Research consortia apply secure edit distance to align DNA sequences across institutional boundaries while preserving patient genomic privacy.

Computes edit distance on nucleotide sequences to identify mutations
Enables rare disease research across hospitals without centralizing sensitive genetic data
Supports GDPR-compliant collaborative bioinformatics

Census and Population Record Linkage

National statistical agencies use secure edit distance to link census records across decades while protecting citizen identities.

Matches names with spelling variations and typographical errors across time
Enables longitudinal demographic studies without re-identification risk
Supports evidence-based policy while maintaining statistical confidentiality

Fraud Detection Across Institutions

Banks and insurers collaboratively detect synthetic identity fraud by computing edit distance on application data without sharing customer PII.

Identifies slight variations in names, addresses, and phone numbers used to create fake identities
Enables consortium fraud detection while respecting data localization laws
Reduces false positives in identity verification pipelines

PRIVATE STRING COMPARISON PROTOCOLS

Secure Edit Distance vs. Other Private Comparison Methods

A technical comparison of cryptographic protocols used to compute string similarity metrics between two parties without revealing the underlying private strings.

Feature	Secure Edit Distance	Private Set Intersection	Phonetic Encoding (PPRL)
Primary Metric Computed	Levenshtein / Damerau-Levenshtein distance	Jaccard similarity of token sets	Phonetic hash equality (e.g., Soundex)
Cryptographic Paradigm	Garbled Circuits / Secret Sharing	Diffie-Hellman / Oblivious Transfer	Salted Hash with Bloom Filters
Handles Typographical Errors
Handles Phonetic Variations
Output Revealed to Parties	Integer edit distance value	Intersection set or cardinality	Match / Non-match decision
Computational Complexity	O(n*m) per comparison	O(n) per element hashing	O(k) per encoding
Resistant to Frequency Attacks
Suitable for Fuzzy Blocking

Enabling Efficiency, Speed & Accuracy

Intelligent Analysis, Decision & Execution

We build AI systems for teams that need search across company data, workflow automation across tools, or AI features inside products and internal software.

Talk to Us

Search across company data

Give teams answers from docs, tickets, runbooks, and product data with sources and permissions.

Useful when people spend too long searching or get different answers from different systems.

Enterprise searchRAGPermissions

Automate internal workflows

Use AI to route work, draft outputs, trigger actions, and keep approvals and logs in place.

Useful when repetitive work moves across multiple tools and teams.

AI agentsWorkflow automationGovernance

Add AI to products and internal tools

Build assistants, guided actions, or decision support into the software your team or customers already use.

Useful when AI needs to be part of the product, not a separate tool.

AI integrationDecision supportModel routing

PRIVACY-PRESERVING RECORD LINKAGE

Related Terms

Explore the cryptographic and algorithmic building blocks that enable secure edit distance computation and private string comparison.

Bloom Filter Encoding

A probabilistic data structure used to encode sensitive identifiers like names into a bit-array using multiple hash functions. Secure edit distance protocols often operate on these encoded representations to enable approximate matching while resisting cryptanalysis. The q-gram representation of strings can be mapped into Bloom filters, allowing parties to compute similarity metrics without revealing the original plaintext.

EXPLORE

Private Set Intersection Cardinality

A cryptographic protocol that allows two parties to learn only the size of the intersection of their private sets. In the context of secure edit distance, PSI-CA can be used to compute the number of shared q-grams between two strings without revealing which specific q-grams matched. This serves as a building block for approximating string similarity metrics privately.

Locality-Sensitive Hashing

An algorithmic technique that hashes similar input items into the same buckets with high probability. LSH is critical for private blocking in record linkage, drastically reducing the number of string pairs that require full secure edit distance computation. By grouping candidate matches efficiently, LSH makes secure multi-party string comparison computationally feasible at scale.

Homomorphic Encryption

A cryptographic scheme that allows computation directly on encrypted data. Secure edit distance protocols leverage additively homomorphic encryption to compute the minimum number of insertions, deletions, and substitutions between two strings without decrypting either party's input. This enables private dynamic programming over ciphertexts.

Garbled Circuits

A foundational secure multi-party computation primitive where a function is represented as a Boolean circuit and evaluated without revealing inputs. Secure edit distance can be implemented using garbled circuits to compute the Levenshtein distance matrix privately. Each edit operation is encoded as a circuit gate, and the final distance is revealed without exposing the strings.

Jaro-Winkler Distance

A string similarity metric optimized for short strings like personal names, giving higher scores to strings with matching prefixes. In privacy-preserving record linkage, secure computation protocols can be adapted to compute Jaro-Winkler similarity instead of edit distance when matching names, as it better handles typographical variations common in human-entered data.

About the author

Prasad Kumkar

CEO & MD, Inference Systems

Prasad Kumkar is the CEO & MD of Inference Systems and writes about AI systems architecture, LLM infrastructure, model serving, evaluation, and production deployment. Over 5+ years, he has worked across computer vision models, L5 autonomous vehicle systems, and LLM research, with a focus on taking complex AI ideas into real-world engineering systems.

His work and writing cover AI systems, large language models, AI agents, multimodal systems, autonomous systems, inference optimization, RAG, evaluation, and production AI engineering.

Limited slotsGet a Free AI Consultation

How We Work

Custom AI workflows for your Business

One-fit-all AI don't work for modern businesses. At Inferensys, we aim to understand your business & custom requirements; which we use to define most efficient agentic workflows, the data, and the tools for your business.