Efficient and Precise Secure Generalized Edit Distance and Beyond
Ruiyu Zhu, Yan Huang · IEEE Transactions on Dependable and Secure Computing · 2020
Secure string-comparison by some non-linear metrics such as edit-distance and its variations is an important building block of many applications including patient genome matching and text-based intrusion detection. Despite the significance of these string metrics, computing them in a provably secure manner is very expensive. In this article, we improve the performance of secure computation of these string metrics without sacrificing security, generality, composability, and accuracy. We explore a new design methodology that allows us to reduce the asymptotic cost by a factor of$O(\log n)$O(logn)(where$n$ndenotes the input string length). In our experiments, we observe up to an order-of-magnitude savings in time and bandwidth compared to the best prior results. We have also extended our semi-honest protocols to work in the malicious model.