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

Wouter Legiest, Jan-Pieter D’Anvers, Bojan Spasic, Nam-Luc Tran and Ingrid Verbauwhede · 2025

Read Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell by Wouter Legiest, Jan-Pieter D’Anvers, Bojan Spasic, Nam-Luc Tran and Ingrid Verbauwhede (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-14568.txt.

Introduction

Wouter Legiest and co-authors sped up a private text comparison in this 2025 cryptography paper. Edit distance measures how many changes turn one string into another, and it drives jobs from DNA alignment to finance. Fully homomorphic encryption lets a server compute on locked data it cannot read. The catch is cost: each cell of the classic grid needed about ninety-four costly refresh steps.

Their method, Leuvenshtein, cuts that to a single refresh per cell. A separate trick checks whether two characters match in just two steps. Overall speed rose up to 278 times over the best prior locked-data version. When one string can sit unencrypted on the server, pre-work adds a further threefold gain.

Catalog record

CREATORWouter Legiest, Jan-Pieter D’Anvers, Bojan Spasic, Nam-Luc Tran and Ingrid Verbauwhede
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-14568

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell Wouter Legiest, Jan-Pieter D’Anvers, Bojan Spasic, Nam-Luc Tran and Ingrid Verbauwhede Abstract This paper presents a novel approach to calculating the Levenshtein (edit) distance within the framework of Fully Homomorphic Encryption (FHE), specifically targeting third-generation schemes like TFHE. Edit distance computations are essential in applications across finance and genomics, such as DNA sequence alignment. We introduce an optimised algorithm that significantly reduces the cost of edit distance calculations called Leuvenshtein. This algorithm specifically reduces the number of programmable bootstraps (PBS) needed per cell of the calculation, lowering it from approximately 94 operations – required by the conventional Wagner-Fisher algorithm – to just 1. Additionally, we propose an efficient method for performing equality checks on characters, reducing ASCII character comparisons to only 2 PBS operations. Finally, we explore the potential for further performance improvements by utilising preprocessing when one of the input strings is unencrypted. Our Leuvenshtein achieves up to 278 × 278\times faster performance compared to the best available TFHE implementation and up to 39 × 39\times faster than an optimised implementation of the Wagner-Fisher algorithm. Moreover, when offline preprocessing is possible due to the presence of one unencrypted input on the server side, an additional 3 × 3\times speedup can be achieved. 1 Introduction The past 20 years have seen a major evolution of the global financial system. Financial crises, geopolitical events and economic growth have deeply impacted the direction that banking regulations have taken. One of the major policy shifts is in the direction of increasing transparency and sharing information between financial institutions. For instance, the G20 set targets for cross-border payments [ 12 ] formulating objectives for enhancing cost, speed, financial inclusion and transparency in an effort to guarantee efficiency and seamlessness of an interconnected financial system. In line with the PSD2 directive [ 10 ] , which initiated the open-banking initiative in Europe, the EU has recently proposed the Financial Data Access framework which will grant consumers and SMEs to authorise third parties to access their data held by financial institutions. Information sharing among financial institutions is seen as paramount in the fight against financial crime and money laundering [ 17 ] , and is also expected to drive GDP gains of major economies [ 11 ] . In the previously mentioned initiatives, success can only be achieved if trust is built among all the actors. Trust can only be built if security and privacy are guaranteed in the exchange of information. While the directives are clear, the means to achieve a successful implementation are left to the actors proposing the services and products. Considering the recent legislative proposal to make Euro payments instant [ 11 ] , there is an obligation for payment providers to verify the match between the bank account number and the name of the beneficiary provided by the payer, as well as to alert the payer of possible mistakes or suspected fraud before the payment is made. In such applications, string similarity calculations are ubiquitous to provide robustness against spelling errors [ 3 ] . One example is the edit distance, which calculates the minimum number of edits between two given strings. Recently, technologies enabling computation on encrypted data, namely fully homomorphic encryption (FHE) have become more practical. Informally, FHE is an encryption scheme that enables a data owner to securely outsource computation on their data to an untrusted processing party, whereby the processing party computes over encrypted data and stays oblivious of the data and the computed result. The utility of FHE comes at a performance price, which can sometimes be prohibitive for time-critical applications. However, the recent advances in software [ 7 ] and hardware [ 14 , 29 ] implementation of the underlying FHE algorithms show promising performance results, encouraging the practitioners to start including FHE in production. FHE schemes fall into two main categories: second-generation schemes like BGV [ 5 ] , BFV [ 13 ] , and CKKS [ 8 ] support parallel computations on batched ciphertexts but have larger ciphertexts and slower bootstrapping. Third-generation schemes like TFHE [ 6 ] prioritise speed with smaller ciphertexts and faster bootstrapping, though they work on small, individual messages and require bootstrapping for nearly every operation. TFHE also allows any function to be applied ‘for free’ during bootstrapping, making it ideal for fast, logic-based encrypted computations. In the context of string matching for financial applications, FHE could pose as an important enabler [ 18 ] . Instead of physically sharing their customer information, parties could compute the desired outcome of the matching operation avoiding data sharing in clear altogether. The institution sending the payment would encrypt the transaction data using a suitable FHE scheme, and send it to a third party which would compute the desired matching score in the encrypted domain and return the encrypted result. This result (and any intermediate variable) can only be decrypted by the payer institution. In the process, according to the principles of FHE, the third party provably does not learn anything about the transaction data, and the institution sending the payment does not learn anything about the customers of the institution receiving the payment. Another interesting application of approximate string matching is in secure and privacy-preserving DNA analysis. Approximate string matching is essential in DNA analysis, where genetic sequences must be matched while allowing for slight discrepancies due to mutations. This flexibility is vital for detecting similar sequences that may vary because of natural mutations or sequencing errors. Cheon et al. [ 9 ] provided the first edit distance algorithm in the context of somewhat homomorphic encryption. They develop both equality check and min functions and use this to build up edit distance calculation. They also give a thorough analysis of the homomorphic depth of their solution. Their methods were later generalised by Vanegas et al. [ 28 ] , elaborated for an MPC context. Later, Aziz et al. [ 1 ] , Asharov et al. [ 2 ] and Zheng et al. [ 34 ] proposed an approximation of the edit distance for genome analysis for fully homomorphic encryption. All the above techniques are based on second-generation FHE schemes and are built around arithmetic ciphertexts. Edit distance calculations for third-generation FHE schemes are less well-researched. Recently, ZAMA showed an edit distance calculation for TFHE as a demonstration of the concrete compiler [ 32 ] . This demonstrator is based on high-level code (i.e., Python) that is transformed to TFHE by the concrete compiler, and the implementation uses a recursive definition of the edit distance. 1.1 Our contribution In this paper, we develop a new edit distance algorithm for third-generation FHE schemes. We develop a new algorithm adapted to TFHE, which we call Leuvenshtein, and use this to show that the properties of the programmable bootstrapping play very well with edit distance calculations. The main ideas of our implementation are: 1. Small representations : We use differential values that represent the differences between intermediate results, instead of working on the intermediate results themselves. This reduces the size of the intermediate variables, leading to a smaller representation and more efficient calculations, significantly reducing the PBS costs. The size of our intermediate representations

Read the complete text