ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (10): 2125-2133.doi: 10.7544/issn1000-1239.2018.20180418

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

Previous Articles     Next Articles

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

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

CLC Number: