字符串模式匹配的安全多方计算  

Secure Multiparty String Matching Computation

作　　者：亢佳 李顺东[1] 杨晓艺[1] 

机构地区：[1]陕西师范大学计算机科学学院,西安710119

出　　处：《密码学报》2017年第3期241-252,共12页Journal of Cryptologic Research

基　　金：国家自然科学基金项目(61272435)

摘　　要：安全多方计算是近年来国际密码学界研究的热点问题之一,是信息社会隐私保护的核心技术.很多研究者已经对其进行了深入研究,并提出了各种各样的具有实际应用背景的安全多方计算问题以及它们的解决方案.本文研究字符串模式匹配的安全多方计算问题.保密地判断字符串模式匹配问题是安全多方计算的一个重要组成部分,在信息检索、信息过滤、入侵检测、病毒检测、计算生物学等方面有重要的意义,同时在拍卖,招标等其他商业领域也有广泛的应用前景.为了保密地判断两个字符串是否模式匹配,本文首先借助Goldwasser-Micali异或同态加密算法设计了判断两个字符串是否相等的协议;然后基于BMH算法提出了高效的字符串模式匹配协议;最后将字符串模式匹配问题转化成集合成员判定问题,设计了保密性更好,计算复杂性和通信复杂性更低的新协议.利用模拟范例对以上协议做出了安全性分析,并证明了协议是正确的.同时给出了以上协议计算复杂性和通信复杂性的理论分析,通过真实数据集实验验证了以上协议的高效性.Secure multiparty computation is a research focus in the international cryptographic community and a key privacy preserving technique in cyberspace. A variety of SMC problems and relative solutions have been presented in public literatures. This paper studies an SMC problem of privacy-preserving string matching. As an important case of secure multi-party computation, it has important theoretical significance and broad applications in auction, bidding and some other electronic commerce activities. To privately determine whether two strings match, based on the XOR homomorphism of Goldwasser-Micali probabilistic encryption algorithm, we first present a protocol to determine whether two strings are equal. Then we propose a protocol to privately determine whether two strings match based on BMH algorithm with higher efficiency. Finally, we design a more efficient and more secure protocol by changing two strings matching problem into set-inclusion problem. In addition, we prove that these protocols are secure using simulation paradigm in the semi-honest model and analyze their correctness. We also analyze the computational complexities and communication complexities of the proposed protocols and show that these protocols are efficient.

关 键 词：密码学 安全多方计算 字符串相等 字符串模式匹配 

分 类 号：TN918.4[电子电信—通信与信息系统]