Efficient and Precise Secure Generalized Edit Distance and Beyond.

Area of Science:

• Computer Science
• Cryptography
• Bioinformatics

Background:

• Secure string comparison using metrics like edit-distance is crucial for applications such as patient genome matching and intrusion detection.
• Current methods for provably secure computation of these metrics are computationally expensive, limiting their practical use.
• Existing protocols often face trade-offs between security, performance, and generality.

Purpose of the Study:

• To enhance the performance of secure computation for non-linear string metrics without compromising security, generality, composability, or accuracy.
• To introduce a novel design methodology for reducing the asymptotic cost of secure string comparison.
• To develop the most efficient actively-secure protocols for computing string metrics in the malicious model.

Main Methods:

• Exploration of a new design methodology to reduce computational complexity by a factor of O(log n), where n is the input string length.
• Extension of semi-honest protocols to the malicious model, ensuring security against adversarial behavior.
• Experimental evaluation to quantify performance improvements in terms of time and bandwidth.

Main Results:

• Achieved a reduction in asymptotic cost by a factor of O(log n) for secure string metric computation.
• Observed up to an order-of-magnitude savings in time and bandwidth compared to state-of-the-art prior results.
• Developed the most efficient actively-secure protocols for computing string metrics in the malicious model.

Conclusions:

• The proposed methodology significantly improves the efficiency of secure string comparison protocols.
• The new protocols offer substantial performance gains while maintaining high levels of security and accuracy.
• This work provides a more practical and efficient solution for secure string matching in sensitive applications.