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

Learn about a groundbreaking approach to computing Levenshtein edit distance using Fully Homomorphic Encryption (FHE) in this 14-minute conference presentation from USENIX Security '25. Discover how researchers from COSIC at KU Leuven and SWIFT have developed the "Leuvenshtein" algorithm that dramatically reduces computational costs for edit distance calculations in encrypted data environments. Explore the technical breakthrough that reduces programmable bootstrap operations from 94 per cell in conventional Wagner-Fisher algorithms to just 1, while also implementing efficient ASCII character comparison methods requiring only 2 PBS operations. Understand the practical applications in finance and genomics, particularly for DNA sequence alignment, and examine how this optimization achieves up to 278x faster performance compared to existing TFHE implementations. Gain insights into preprocessing techniques that can provide additional 3x speedup when one input string remains unencrypted on the server side, making privacy-preserving string comparison significantly more practical for real-world applications.