An Efficient and Secure Three-Party Wildcard Pattern Matching Protocol

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.