Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single...
summary
Leuvenshtein implements edit distance inside TFHE-style FHE by rewriting the cell recurrence into a 16-entry lookup so each cell evaluates with single PBS per cell instead of ~94, and it replaces naïve byte comparisons with 2 PBS equality checks for ASCII. Prototype code beats a Zama-compiled baseline (240s → 2.3s, week → 35min) and reports up to 278x faster than the best TFHE implementation and ~39x over optimized Wagner–Fisher; optional preprocessing gives another 3x.
AI-written summary · about
chapters (10)
- 0:00Leuvenshtein intro
- 0:54TFHE encryption overview
- 2:20Edit vs Hamming distance
- 3:49Edit distance operations
- 4:53Wagner Fisher algorithm
- 7:02Meyers algorithm
- 8:27Homomorphic cell evaluation
- 9:53Character equality check
- 11:39Performance vs Zama
- 13:26Conclusion
related talks
47mHomomorphic Encryption
38mPrivacy in the Open Source: Homomorphic Encryption
21mCut Tracing with E-Graphs for Boolean FHE Circuit Synthesis
20mA Tensor Compiler with Automatic Data Packing for Simple and Efficient Fully Homomorphic(…)
44mIP Protection and Privacy in LLM: Leveraging Fully Homomorphic Encryption
20mAugmenting EVMs with FHE to Enable New Use Cases
34mBuilding private and secure applications easily.
22mLocality-Preserving Hashing for Shifts with Connections to Cryptography