Faster Privacy-Preserving Computation of Edit Distance with Moves
This work addresses the need for secure and efficient string similarity computation, particularly for sensitive data like DNA sequences, but it is incremental as it builds on prior methods to improve performance.
The paper tackles the problem of efficiently computing an extended edit distance measure between two strings in a privacy-preserving two-party setting, resulting in a protocol that significantly reduces round complexity while maintaining cryptographic strength, with performance improvements demonstrated for DNA sequences.
We consider an efficient two-party protocol for securely computing the similarity of strings w.r.t. an extended edit distance measure. Here, two parties possessing strings $x$ and $y$, respectively, want to jointly compute an approximate value for $\mathrm{EDM}(x,y)$, the minimum number of edit operations including substring moves needed to transform $x$ into $y$, without revealing any private information. Recently, the first secure two-party protocol for this was proposed, based on homomorphic encryption, but this approach is not suitable for long strings due to its high communication and round complexities. In this paper, we propose an improved algorithm that significantly reduces the round complexity without sacrificing its cryptographic strength. We examine the performance of our algorithm for DNA sequences compared to previous one.