Leuvenshtein：基于 FHE 的高效编辑距离计算，每个单元格仅需一次自举

本文提出了一种在全同态加密 (FHE) 框架内计算 Levenshtein（编辑）距离的新方法，特别针对 TFHE 等第三代方案。编辑距离计算在金融和基因组学等应用中至关重要，例如 DNA 序列比对。我们引入了一种优化算法，称为 Leuvenshtein，它显著降低了编辑距离计算的成本。该算法特别减少了计算的每个单元格所需的程序化自举 (PBS) 操作次数，将其从传统 Wagner-Fisher 算法所需的约 94 次操作降低到仅 1 次。此外，我们提出了一种执行字符相等性检查的高效方法，将 ASCII 字符比较减少到仅 2 次 PBS 操作。最后，我们探讨了当其中一个输入字符串未加密时，利用预处理进行进一步性能改进的潜力。与最佳的 TFHE 实现相比，我们的 Leuvenshtein 实现了高达 278 倍的性能提升，与 Wagner-Fisher 算法的优化实现相比，则高达 39 倍。此外，当由于服务器端存在一个未加密的输入而可能进行离线预处理时，还可以实现额外的 3 倍加速。