Practical Single-Round Secure Wildcard Pattern Matching

Previous studies introduce various approaches for the WPM problem but requires at least a two-round protocol or computation cost linear to input length. Oriented to applications in the client-server mode, however, existing solutions are not practical and efficient enough. Therefore we focus on the round and computation complexity of the WPM. In this paper, under the semi-honest model, we propose a single-round secure WPM protocol based on oblivious transfer (OT) and secret sharing schemes. The insight of our proposed protocol is the reduction from the WPM to the process of secret sharing and reconstruction in a novel way. We provide a customized OT construction and apply the OT extension technique to the protocol, where the client and the server need merely a constant number of public key operations in a round of communication. In addition, we prove the security of the protocol in the ideal/real simulation paradigm and evaluate the performance. Compared to existing secure WPM protocols, both theoretical and experimental results show that our protocol is more practical.