一个高效的安全两方近似模式匹配协议

近似模式匹配是模式匹配中最适合实际应用的变体之一，其功能是确定2个字符串之间的汉明距离是否小于某给定阈值.由于其实用性，近似模式匹配在人脸识别、基因匹配等方面具有广泛的应用.然而，由于私有数据的敏感性，数据拥有者往往不愿意共享其隐私数据.幸运的是，安全近似模式匹配可以在不泄露数据前提下完成匹配功能.首次基于茫然传输(oblivious transfer, OT)、同态加密(homomorphic encryption, HE)、茫然多项式计算(oblivious polynomial evaluation, OPE)以及隐私等值比较(private equality test, PEQT)技术提出了安全的、实用的近似模式匹配协议，并通过理想/现实模拟范式证明协议具有半诚实敌手安全性.就效率而言，与当前已有的安全近似模式匹配工作相比，协议在计算复杂度方面具有优势，将复杂度从O(nm)降为O(nτ)，其中n为文本长度，m为模式长度，τ为给定阈值.最后，为了检验高效性，对协议进行了性能评估.实验结果表明：当模式长度为2+6且文本长度为2+{12}时，协议仅需要10 s运行时间.

An Efficient Secure Two-Party Approximate Pattern Matching Protocol

Approximate pattern matching (APM) is the most suitable for practical applications among the variants of pattern matching, whose function is to determine whether the Hamming distance between two strings is less than a given threshold value. Due to its practicality, APM has a wide range of applications in face recognition, gene matching, etc. However, owing to the sensitivity of private data, data owners are often reluctant to share their private data. Fortunately, secure approximate pattern matching (SAPM) can accomplish the matching function without revealing the data. In this paper, we propose a secure and practical approximate pattern matching protocol based on oblivious transfer (OT), homomorphic encryption (HE), oblivious polynomial evaluation (OPE) and private equality test (PEQT) for the first time, and demonstrate that the protocol has semi-honest adversary security through ideal/realistic simulation paradigm. In terms of efficiency, compared with currently available secure approximate pattern matching works, our protocol has an advantage in the aspect of computation complexity by reducing the complexity from O(nm) to O(nτ), where n is the text length, m is the pattern length, and τ is a given threshold value. Finally, to examine the efficiency, we evaluate the performance of the protocol. The performance result shows that the protocol takes only 10 s to run when the pattern length is 2+6 and the text length is 2+{12}.