Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell

Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell

Speakers: Wouter Legiest

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=ysvbuWkbhnQ

Overview

The talk "Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell," presented by Wouter Legiest, introduces a groundbreaking new algorithm for calculating edit distance in the Fully Homomorphic Encryption (FHE) domain. This joint work with Yan Peter Buan Nluk and Ingret addresses a critical challenge in privacy-preserving data analysis: efficiently determining the similarity between two strings without ever decrypting them. The ability to compute edit distance on encrypted data has profound implications for applications requiring sensitive string comparisons, such as DNA matching, secure name matching for identity verification, and privacy-preserving optical character recognition (OCR) correction.

Traditional methods for calculating edit distance are computationally intensive, and performing these operations directly on encrypted data using FHE has historically been prohibitively slow. The Leuvenshtein algorithm, named as a play on Levenshtein distance, tackles this by developing a novel, highly optimized approach specifically tailored for the TFHE (Toroidal FHE) scheme. By drastically reducing the number of expensive bootstrapping operations, the Leuvenshtein team has achieved unprecedented performance gains, making privacy-preserving string similarity calculations significantly more practical and opening new avenues for secure data processing in privacy-sensitive sectors.

Background

▶ Watch: Introduction to Leuvenshtein and talk overview (0:00)

To understand the significance of the Leuvenshtein algorithm, it's essential to first grasp the fundamentals of edit distance and the underlying homomorphic encryption scheme. Homomorphic Encryption (HE) allows computations to be performed directly on encrypted data, yielding an encrypted result that, when decrypted, matches the result of the same computation performed on the plaintext. Fully Homomorphic Encryption (FHE) extends this to arbitrary computations, but typically at a significant performance cost, primarily due to a process called bootstrapping, which refreshes noisy ciphertexts and is the most computationally expensive operation in FHE.

The Leuvenshtein project leverages TFHE, a boolean-branch FHE scheme particularly well-suited for encrypting small integers into individual ciphertexts. The speakers specifically chose a 4-bit plaintext space, striking a balance between plaintext capacity and the complexity of lookup table evaluations. A key feature of TFHE is its programmable bootstrapping (PBS) mechanism, which allows for the evaluation of a custom lookup table (LUT) during the bootstrap process. While TFHE natively supports 16-element LUTs, its negacyclic properties can be exploited to effectively support 32-element LUTs, though the upper 16 elements are deterministically defined by the lower 16. This unique property forms the cornerstone of their optimization.

The core problem Leuvenshtein addresses is the edit distance, a metric quantifying the dissimilarity between two strings by counting the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one string into the other. Unlike Hamming distance, which only counts mismatches at corresponding positions and fails for strings of different lengths or with shifted characters (e.g., "Sabbath" vs. "Sabbaton"), edit distance provides a more robust similarity measure. For example, to transform "kitten" into "sitting," one needs to substitute 'k' for 's', insert 'i', and substitute 'e' for 'a', resulting in an edit distance of 3. This makes it invaluable for tasks like DNA sequence alignment, spell checking, and fuzzy string matching.

Calculating edit distance is traditionally done using dynamic programming algorithms. The most common is the Wagner-Fischer algorithm, which builds a matrix where each cell (i, j) stores the edit distance between the first i characters of string A and the first j characters of string B. Each cell's value is determined by the minimum of three previous cells: the cell above (representing a deletion), the cell to the left (representing an insertion), and the diagonal cell (representing a substitution), with an additional cost if the characters at (i, j) are different. Specifically, D[i,j] = min(D[i-1,j] + 1, D[i,j-1] + 1, D[i-1,j-1] + cost(A[i], B[j])), where cost(A[i], B[j]) is 0 if A[i] == B[j] and 1 otherwise.

More efficient variants exist, such as Myers' algorithm, which optimizes the Wagner-Fischer approach by observing that adjacent cells in the matrix often differ by only -1, 0, or 1. Instead of storing the full edit distance, Myers' algorithm focuses on storing these differences, often represented as delta V (vertical difference) and delta H (horizontal difference) values. While more efficient in plaintext, adapting Myers' algorithm to the FHE domain presents a significant challenge. The standard cell definition for Myers' algorithm, when translated to a function mapping inputs to an output, requires an 18-value input space (considering delta H, delta V, and character equality). This directly conflicts with TFHE's native 16-element LUT limitation, making a straightforward implementation using a single PBS per cell impossible.

Key Findings

▶ Watch: Understanding Edit Distance: Beyond Hamming (2:08)

The Leuvenshtein project's primary contribution is a novel algorithm that enables the calculation of edit distance with unprecedented efficiency in the TFHE domain. The core innovation lies in a mathematical transformation of the Myers' algorithm cell definition, allowing it to be evaluated using a single Programmable Bootstrapping (PBS) per cell, a dramatic improvement over prior approaches.

Key findings include:

1. Single PBS per Cell Calculation: The researchers devised a method to convert Myers' algorithm's 18-input space cell definition into a form that effectively fits within TFHE's 16-element lookup table during a single PBS operation. This was achieved by strategically leveraging the negacyclic properties of TFHE, where the upper 16 elements of a 32-element LUT are implicitly defined by the lower 16. By ensuring specific output patterns (two leading and two trailing zeros) in the function's output, they could map the necessary 18 inputs to the available 16 definable LUT elements.
2. Optimized Equality Checking: Beyond the main cell calculation, the team also significantly optimized the character equality checking process. For 7-bit ASCII characters, their method reduces the required PBS operations from a typical five to just two. This is critical as equality checks are performed repeatedly within the edit distance algorithm.
3. Overall PBS Reduction: Combining these innovations, the Leuvenshtein algorithm achieves a remarkable reduction in PBS operations per cell. A straightforward Wagner-Fischer implementation would typically require 94 PBS operations for the cell calculation and 5 for equality checking, totaling 99 PBS per cell. Leuvenshtein reduces this to a mere 3 PBS operations per cell (1 for the main cell calculation, 2 for equality), representing a 33x reduction factor.
4. Exceptional Performance Gains: Practical tests demonstrated substantial speedups compared to generic FHE compilers. For 8-character strings, Leuvenshtein reduced computation time from approximately 240 seconds (using the Zama compiler) to 2.3 seconds. More impressively, for 256-character strings, a task that would take roughly a week with the Zama compiler was completed in only 35 minutes, an acceleration factor of approximately 280x. This highlights the critical need for specialized, hand-tuned FHE algorithms.

Technical Deep Dive

▶ Watch: The Wagner-Fisher Algorithm for Edit Distance (4:16)

The Leuvenshtein algorithm's efficiency stems from a sophisticated understanding and manipulation of TFHE's underlying mechanics, coupled with a clever mathematical reformulation of the edit distance problem.

At the heart of the solution is TFHE (Toroidal FHE), a boolean-branch FHE scheme. TFHE operates on small integers, typically encrypting a few bits (e.g., 4 bits in this work) into individual ciphertexts. A defining characteristic of TFHE is its programmable bootstrapping (PBS), a noise-reduction operation that simultaneously evaluates a lookup table (LUT). This allows for arbitrary functions to be computed on encrypted data. While a standard TFHE LUT has 16 elements (corresponding to all possible inputs for a 4-bit plaintext), the researchers exploit the negacyclic properties of TFHE's underlying polynomial rings. This property means that if you define the first 16 elements of a 32-element function, the subsequent 16 elements are implicitly determined. The Leuvenshtein algorithm leverages this to encode more complex functions than a simple 16-element LUT would typically allow.

The foundational algorithm for edit distance is Wagner-Fischer. It constructs a matrix D where D[i,j] is the edit distance between the first i characters of string A and the first j characters of string B. Each cell D[i,j] is calculated as:

D[i,j] = min(D[i-1,j] + 1, D[i,j-1] + 1, D[i-1,j-1] + cost(A[i], B[j]))

where cost(A[i], B[j]) is 0 if A[i] == B[j] and 1 otherwise. This requires three previous cell values and an equality check. In FHE, calculating min and equality checks are non-trivial and often require multiple PBS operations.

The work builds upon Myers' algorithm, an optimization that focuses on storing differences between adjacent cells (delta V for vertical difference, delta H for horizontal difference), which typically range from -1 to 1. This reduces the size of the values being stored and processed, but its cell update formulas are more complex. When translating Myers' algorithm into a function for a TFHE LUT, the inputs to calculate a new cell (i,j) include delta V, delta H, and the character equality status. delta V and delta H each have three possible outcomes (-1, 0, 1), and equality has two (true, false). This results in 3 3 2 = 18 possible input combinations. The critical challenge is that this 18-input space exceeds TFHE's native 16-element LUT capability.

The Leuvenshtein team's breakthrough was to mathematically convert this 18-input function into a form that could be evaluated with a single PBS. They achieved this by carefully reformulating the function such that its output for two specific "dummy" input combinations (which would never occur in a valid Myers' algorithm computation) resulted in zero. By arranging the function's outputs such that there were two leading zeros and two trailing zeros in the theoretical 18-element output table, they could effectively map the 18 valid inputs onto the 16 freely definable elements of the TFHE LUT. The remaining implicitly defined 16 elements (due to negacyclic properties) would then correctly correspond to the required outputs for the full 18-input function space, making the single PBS evaluation possible. This is a highly specialized FHE optimization that requires deep understanding of TFHE's mathematical structure.

Beyond the core cell calculation, the equality checking mechanism for characters also received significant optimization. For 7-bit ASCII characters, a standard approach might involve multiple bit-wise comparisons and PBS operations. Leuvenshtein employs a two-PBS strategy:

1. Each 7-bit ASCII character is split into two ciphertexts: one for the lowest 4 bits and one for the uppermost 3 bits.
2. To check if two characters C1 and C2 are equal, their corresponding 4-bit (LSB) ciphertexts and 3-bit (MSB) ciphertexts are subtracted.
3. A first PBS is applied to the result of the LSB subtraction. This PBS outputs 0 if the LSBs are equal, and 1 if they are not. This output (0 or 1) is then added to the MSB subtraction result, effectively "flagging" the MSB ciphertext if the LSBs differed.
4. A second PBS is then applied to this modified MSB ciphertext. If the final value in this ciphertext is 0, it means both the LSBs and MSBs were equal. If it's anything else, the characters are not equal. This ingenious method reduces the typical 5 PBS operations for character equality down to just 2.

Combining these two major optimizations—the single PBS per cell calculation and the two-PBS equality check—results in an overall reduction from 99 PBS operations per cell (94 for computation, 5 for equality) to just 3 PBS operations per cell (1 for computation, 2 for equality), a 33x improvement.

Demo / Proof of Concept

▶ Watch: The Challenge: Meyers Algorithm Doesn't Fit TFHE LUT (7:52)

The efficacy of the Leuvenshtein algorithm was rigorously demonstrated through practical implementations and benchmarking against existing FHE compilation frameworks. The speakers presented compelling results by comparing their hand-optimized C++ implementation with a program generated by the Zama compiler. The Zama compiler is a notable tool that translates high-level Python code into FHE programs, representing a state-of-the-art "compiler-driven" approach to FHE.

The tests focused on calculating the edit distance for strings of varying lengths:

1. Short Strings (8 characters): For two 8-character strings, the Zama compiler-generated FHE program took approximately 240 seconds to compute the edit distance. In stark contrast, the Leuvenshtein algorithm completed the same task in a mere 2.3 seconds. This represents a speedup factor of roughly 100x.
2. Longer Strings (256 characters): The performance difference became even more pronounced with longer inputs. Calculating the edit distance for two 256-character strings using the Zama compiler was estimated to take around one week. The Leuvenshtein algorithm, however, achieved this computation in just 35 minutes. This translates to an astounding speedup factor of approximately 280x.

These results unequivocally highlight the significant performance gap between generic FHE compilers and highly specialized, manually optimized FHE algorithms. While FHE compilers are valuable for rapid prototyping and general-purpose FHE development, the Leuvenshtein work demonstrates that for specific, complex operations like edit distance, deep algorithmic and cryptographic optimization remains crucial for achieving practical performance. The speakers emphasized that "there is still a need for manual conversions of all of these algorithms down to the FHE domain" to unlock their full potential.

Defensive Implications

▶ Watch: Leuvenshtein's Solution: Adapting for TFHE Lookup Tables (8:10)

The Leuvenshtein algorithm represents a significant leap forward in the practical application of Fully Homomorphic Encryption (FHE), particularly for privacy-preserving string comparisons. For defenders and security architects, this work has several crucial implications:

1. Enabling Privacy-Preserving Data Operations: The most direct implication is the enhanced feasibility of performing sensitive string similarity checks without exposing plaintext data. This is vital for scenarios involving Privacy-Preserving Record Linkage (PPRL), where organizations need to match or link records (e.g., patient data, financial transactions, law enforcement databases) without revealing personally identifiable information. With Leuvenshtein, edit distance can now be computed on encrypted names, addresses, or medical codes, allowing for robust fuzzy matching while maintaining data confidentiality.
2. Expanding the Scope of Secure Multi-Party Computation (SMC) and Privacy-Enhancing Technologies (PETs): By making FHE-based edit distance practical, Leuvenshtein broadens the types of computations that can be securely performed in multi-party settings. This could include privacy-preserving DNA matching for genetic research, secure search over encrypted documents, or even more advanced OCR correction where the original text never leaves the encrypted domain. Defenders can now consider FHE for a wider array of use cases that previously might have been deemed too computationally expensive.
3. Reducing Data Exposure and Attack Surface: Any computation performed on encrypted data inherently reduces the points at which sensitive information is exposed in plaintext. By allowing complex operations like edit distance to remain in the encrypted domain, organizations minimize the risk of data breaches, insider threats, and unauthorized access during processing. This aligns with the principle of least privilege and data minimization, strengthening overall data security posture.
4. Understanding FHE's Maturation: The dramatic performance improvements showcased by Leuvenshtein signal the increasing maturity and practicality of FHE for specific, well-defined problems. Defenders should recognize that FHE is no longer purely theoretical but is progressing towards real-world deployability for niche, high-value privacy applications. This means security strategies should start to incorporate FHE as a viable tool for specific privacy challenges, rather than dismissing it as too slow.
5. Challenges and Considerations: While promising, FHE still presents challenges. Implementing and deploying FHE solutions requires specialized expertise, as demonstrated by the significant performance difference between generic compilers and hand-tuned algorithms. Defenders need to be aware that while the technology is advancing, its practical application still often demands deep cryptographic and algorithmic knowledge. Furthermore, the selection of the correct FHE scheme (e.g., TFHE for boolean circuits and small integers) is critical for efficiency.

In essence, Leuvenshtein empowers defenders with a powerful new primitive for privacy-preserving data analytics, enabling secure computations on sensitive string data that were previously impractical.

Key Takeaways

• The Leuvenshtein algorithm introduces an efficient FHE-based method for computing edit distance, a crucial metric for string similarity.
• It achieves a groundbreaking single Programmable Bootstrapping (PBS) operation per cell calculation for Myers' algorithm by leveraging TFHE's negacyclic properties and a mathematical reformulation of the cell update function.
• The algorithm includes an optimized 7-bit ASCII character equality check, reducing it from a typical 5 PBS to just 2 PBS operations.
• Overall, Leuvenshtein reduces the number of PBS operations per cell by a factor of 33x, from 99 down to 3.
• Practical benchmarks demonstrated a significant performance boost, achieving up to a 280x speedup compared to FHE programs generated by the Zama compiler for 256-character strings (reducing computation from a week to 35 minutes).
• This work makes privacy-preserving string similarity computations significantly more practical, enabling secure applications in areas like DNA matching, identity verification, and OCR correction without decrypting sensitive data.

About the Speaker(s)

Wouter Legiest is one of the researchers behind the Leuvenshtein algorithm, a novel method for efficient FHE-based edit distance computation. He presented this work at USENIX Security, highlighting his expertise in homomorphic encryption and its application to complex cryptographic problems. The Leuvenshtein project is a collaborative effort, with Wouter Legiest as a key contributor alongside Yan Peter Buan Nluk and Ingret, as mentioned during the presentation. His talk underscored the importance of specialized algorithmic design in pushing the boundaries of practical FHE performance.