ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2018, Vol. 55 ›› Issue (10): 2125-2133.doi: 10.7544/issn1000-1239.2018.20180418

所属专题: 2018分布式安全与区块链技术研究专题

• 信息安全 • 上一篇    下一篇



  1. (山东师范大学信息科学与工程学院 济南 250358) (
  • 出版日期: 2018-10-01
  • 基金资助: 

An Efficient and Secure Three-Party Wildcard Pattern Matching Protocol

Wei Xiaochao, Zheng Zhihua, Wang Hao   

  1. (School of Information Science and Engineering, Shandong Normal University, Jinan 250358)
  • Online: 2018-10-01

摘要: 安全多方计算(secure multiparty computation, SMPC)是实现分布式计算安全的重要技术,其主要考虑在多个相互独立的实体之间协同完成某项任务的计算,同时要实现输入信息的隐私保护.模式匹配在信息检索、生物工程、人脸识别等领域有着广泛应用,在实现匹配功能的同时保证查询模式及结果的隐私是当下研究的重点.带通配符模式匹配是模式匹配的一种类型,其允许查询模式中可以存在某些通配符信息,因此能够实现某一类信息的批量查询.传统的安全带通配符模式匹配协议中主要涉及数据库方和查询方2个实体,鉴于当下数据共享技术的发展,这种模型难以刻画更多的应用场景.以实际应用出发,首次在三方场景下研究安全带通配符模式匹配协议的构造.首先考虑一个具体的安全三方带通配符模式匹配功能函数,并给出其形式化描述和功能性分析;然后,基于秘密分享(secret sharing)和外包茫然传输协议(outsourced oblivious transfer, OOT)在半诚实敌手模型下给出协议构造,并通过茫然传输扩展(oblivious transfer extension)技术提高协议效率,协议仅需要3轮交互,且计算和通信复杂度为O(k)和O(nm),其中n和m是2个数据提供方的输入长度,k是实现OT扩展协议的基数,其值远小于nm.

关键词: 安全多方计算, 带通配符模式匹配, 外包OT协议, 秘密分享, OT扩展

Abstract: Secure multiparty computation is an important technique used to achieve distributed security, which mainly considers the cooperative computing between many distinct participants meanwhile guaranteeing the privacy of the input information. Pattern matching has wide application in information retrieval, bioengineering and facial recognition. How to protect the privacy of the retrieval pattern and result when achieving the matching function has attracted more and more attention of the researchers. As a variant of pattern matching, wildcard pattern matching enables the existence of wildcard in the retrieval pattern, such that batch retrieval can be achieved for information with same characteristics. Traditional secure wildcard pattern matching involves only two parties, which are database and user. However, in view of the development of data sharing technique, the above model cannot describe many new application scenarios. In this paper, we firstly research secure three-party wildcard pattern matching for some specific applications. At first, we propose a formal description of a concrete secure three-party wildcard pattern matching functionality and analyze its function. Then, we construct a protocol using secret sharing and outsourced oblivious transfer (OOT) in semi-honest model. Using oblivious transfer extension technique, our protocol requires only 3 rounds, and the computation and communication complexity is respectively O(k) and O(nm), where n and m are the lengths of the data providers, and k is the basic number of OT extension which is much less than nm.

Key words: secure multiparty computation, wildcard pattern matching, outsourced oblivious transfer (OT) protocol, secret sharing, oblivious transfer (OT) extension