Paper 2025/012
Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell
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 28 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 utilizing preprocessing when one of the input strings is unencrypted. Our Leuvenshtein achieves up to $205\times$ faster performance compared to the best available TFHE implementation and up to $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\times$ speedup can be achieved.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- TFHEFHECGGIEdit distance
- Contact author(s)
-
wouter legiest @ esat kuleuven be
janpieter danvers @ esat kuleuven be
ingrid verbauwhede @ esat kuleuven be - History
- 2025-01-04: revised
- 2025-01-03: received
- See all versions
- Short URL
- https://ia.cr/2025/012
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/012,
author = {Wouter Legiest and Jan-Pieter D'Anvers and Bojan Spasic and Nam-Luc Tran and Ingrid Verbauwhede},
title = {Leuvenshtein: Efficient {FHE}-based Edit Distance Computation with Single Bootstrap per Cell},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/012},
year = {2025},
url = {https://eprint.iacr.org/2025/012}
}