We propose the first two-party protocol for securely computing an extended edit distance. The parties possessing their respective strings x and y want to securely compute the edit distance with move operations (EDM), that is, the minimum number of insertions, deletions, renaming of symbols, or substring moves required to transform x to y. Although computing the exact EDM is NP-hard, there exits an almost linear-time algorithm within the approximation ratio O(lg* N lg N) for N = max{|x|, |y|}, We extend this algorithm to the privacy-preserving computation enlisting the homomorphic encryption scheme so that the party can obtain the approximate EDM without revealing their privacy under the semi-honest model.
展开▼
机译：我们提出了第一个两方协议，用于安全地计算扩展的编辑距离。拥有各自的字符串x和y的参与方希望通过移动操作（EDM）安全地计算编辑距离，即，将x转换为y所需的最小插入，删除，符号重命名或子字符串移动的次数。尽管计算精确的EDM是NP难的，但是对于N = max {| x |，| y |}，在近似比O（lg * N lg N）内存在几乎线性时间算法，我们将此算法扩展到采用同态加密方案的隐私保护计算，使一方可以在半诚实模型下获得近似的EDM而无需透露其隐私。
展开▼
