Zhu Ruiyu, Huang Yan
IU Bloomington, with main research focus in applied cryptography, Indiana University, Bloomington.
Computer Science at Indiana University Bloomington.
IEEE Trans Dependable Secure Comput. 2022 Jan-Feb;19(1):579-590. doi: 10.1109/tdsc.2020.2984219. Epub 2020 Apr 2.
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 paper, 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 (log ) (where denotes 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 extended our semi-honest protocols to work in the malicious model, which is by-far the most efficient actively-secure protocols for computing these string metrics.
通过一些非线性度量（如编辑距离及其变体）进行安全的字符串比较，是许多应用（包括患者基因组匹配和基于文本的入侵检测）的重要组成部分。尽管这些字符串度量很重要，但以可证明安全的方式计算它们成本非常高。在本文中，我们在不牺牲安全性、通用性、可组合性和准确性的前提下，提高了这些字符串度量的安全计算性能。我们探索了一种新的设计方法，使我们能够将渐近成本降低(log )倍（其中 表示输入字符串长度）。在我们的实验中，与之前最好的结果相比，我们观察到时间和带宽节省了一个数量级。我们将半诚实协议扩展到恶意模型中工作，这是迄今为止计算这些字符串度量最有效的主动安全协议。
