摘要
安全多方计算是密码学界研究的热点问题,保密判断字符串匹配是安全多方计算的常见问题之一,其在文本处理领域中是非常重要的一个主题.它可以用于数据处理、数据压缩、文本编辑、信息检索等多种应用中.现有含通配符的字符串保密匹配算法大多数只能实现近似匹配,且通配符的使用受个数、位置的限制,使用不灵活.本文设计了一种新的编码方法,应用该编码方法和Paillier加法同态加密算法,在半诚实模型下设计了字符串模式匹配的保密判定协议和含通配符的字符串保密匹配协议,尤其是第二个协议有一些非常理想的特征,字符串中可以包含零、一个或多个通配符,通配符可以位于字符串的任意位置,一个通配符可以代表任意数量的字符.协议可以保密地实现字符串的精确匹配,通配符的使用也很灵活.其次,由于协议是基于同态加密而不是Bloom Filter构造的,从而消除了Bloom Filter造成的误判,实现了更高水平的隐私保护.采用模拟范例证明了协议的安全性,效率分析表明所设计的协议是高效的.
Secure multi-party computation is one of the hot issues in international cryptographic community.Secure string matching is a common problem in secure multi-party computation,which is a very important topic in the field of text processing.It has many applications,such as data processing,data compression,text editing,information retrieval.Existing privacy preserving string matching algorithms with wildcards can only achieve approximate matching,and the use of wildcards is limited by number and location,so they are not flexible.In this paper,a new encoding method is designed.By using the new encoding method and Paillier’s additively homomorphic encryption algorithm,secure matching protocols are designed for string pattern and strings with wildcards.The proposed protocols are secure in the semi honest model.In particular,the second protocol has someideal characteristics.The string can contain zero,one or more wildcards,which can appear in any position of the string.A wildcard can represent any number of characters.The protocols designed in this paper can achieve exact matching and the use of wildcards is also flexible.The protocol is based on homomorphic encryption rather than Bloom Filter,so as to eliminate the false probability caused by Bloom Filter.Simulation paradigm is used to prove the security of the protocols,and efficiency analysis shows that the designed protocols are efficient.
作者
张凯鑫
杨晨
李顺东
ZHANG Kai-Xin;YANG Chen;LI Shun-Dong(School of Computer Science,Shaanxi Normal University,Xi’an 710119,China)
出处
《密码学报》
CSCD
2022年第4期619-632,共14页
Journal of Cryptologic Research
基金
国家自然科学基金(61272435)。
关键词
密码学
安全多方计算
字符串匹配
通配符
同态加密
cryptography
secure multi-party computation
string matching
wildcards
homomorphic encryption
