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

来源：计算机研究与发展杂志2022年第8期北京时间：

作者：徐琳,魏晓超,蔡国鹏,王皓,郑志华,

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

关键词：安全近似模式匹配, 茫然传输, 同态加密, 茫然多项式计算, 隐私等值比较,