Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell
Wouter Legiest, Jan-Pieter D'Anvers, Bojan Spasic, Nam-Luc Tran, Ingrid Verbauwhede
2025-08-21
Summary
This paper introduces a super-fast way to calculate how different two strings are, like for comparing DNA, using a special kind of encryption called Fully Homomorphic Encryption. They call their new method Leuvenshtein.
What's the problem?
Figuring out how different two strings are, also known as edit distance, is really important for stuff like matching DNA sequences, but doing it with advanced encryption that lets you compute on encrypted data is usually super slow and requires a ton of complex steps.
What's the solution?
The researchers created a clever new algorithm, Leuvenshtein, that drastically cuts down the number of complicated steps, called programmable bootstraps, needed to do the calculation. It goes from about 94 steps per calculation part down to just 1. They also found a quicker way to check if characters are the same, using only 2 of those complex steps. Plus, they figured out that if one of the strings isn't encrypted yet, you can do some prep work beforehand to make it even faster.
Why it matters?
This research is a big deal because it makes sensitive calculations, like those in finance or genomics where privacy is key, much more practical. Their method is way faster than previous attempts, making these advanced computing methods more usable for real-world problems.
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 278times faster performance compared to the best available TFHE implementation and up to 39times 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 3times speedup can be achieved.