Approximate Two-Party Privacy-Preserving String Matching with Linear Complexity
This work addresses privacy concerns in applications like genome comparison, offering a practical solution for secure string matching, though it is incremental as it builds on existing methods by adding approximation and attack mitigation.
The paper tackles the problem of privacy-preserving string matching between two parties without revealing their strings, by introducing a system that provides a deterministic approximation with linear complexity, non-interactive operation, and no third-party involvement, achieving efficiency suitable for cloud computing.
Consider two parties who want to compare their strings, e.g., genomes, but do not want to reveal them to each other. We present a system for privacy-preserving matching of strings, which differs from existing systems by providing a deterministic approximation instead of an exact distance. It is efficient (linear complexity), non-interactive and does not involve a third party which makes it particularly suitable for cloud computing. We extend our protocol, such that it mitigates iterated differential attacks proposed by Goodrich. Further an implementation of the system is evaluated and compared against current privacy-preserving string matching algorithms.