Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single
  Bootstrap per Cell
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.
68a6ee339e4b49496aac6b65
Wouter Legiest
claimed_verified
2025-08-21T10:30:45.863Z
68a6ee2fae023c92c2721c78
/avatars/39e9ee844dd2a0009cce3f22dc2f9d56.svg
Wout Legi
user
woutLegiest
68a6ee339e4b49496aac6b66
Jan-Pieter D'Anvers
68a6ee339e4b49496aac6b67
Bojan Spasic
68a6ee339e4b49496aac6b68
Nam-Luc Tran
68a6ee339e4b49496aac6b69
Ingrid Verbauwhede
Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single
  Bootstrap per Cell
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.
An optimized algorithm reduces the computational cost of edit distance calculations within Fully Homomorphic Encryption, achieving significant performance improvements over existing methods.
Fully Homomorphic Encryption TFHE Wagner-Fisher algorithm programmable bootstraps ASCII character comparisons