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转换为y所需的最小插入，删除，重命名，或者子字符串移动。虽然计算精确的EDM是NP - 硬，但是对于n = max {| x |，| x |，| y |}，在近似比O（lg * n lg n）内出现几乎线性时算法，我们将该算法扩展到保留了隐私保留计算征募了同性恋加密方案，使方可以获得近似EDM，而不会在半诚实模型下揭示他们的隐私。
展开▼
