Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell
Wouter Legiest
34th USENIX Security Symposium (USENIX Security '25) · Day 3 · Crypto 5: HE, MPC, Oblivious Computation
AI review
Genuine cryptographic engineering work — not a survey, not a concept paper, but a hand-tuned algorithm that squeezes Myers' edit distance into a single TFHE bootstrapping operation by exploiting negacyclic structure in a way that isn't obvious. The 33x PBS reduction and 280x wall-clock speedup over a state-of-the-art compiler are real numbers on real hardware, which is exactly what separates this from the usual FHE hype cycle.