Efficient protocols for private wildcards pattern matching

Tushar Kanti Saha*, Deevashwer Rathee, Takeshi Koshiba


研究成果: Article査読

3 被引用数 (Scopus)


A wildcard character in a pattern adds an additional feature in the field of pattern matching. In this paper, we consider two problems of secure pattern matching (SPM) with wildcards: (i) SPM with repetitive wildcards (SPM-RW) and (ii) SPM with compound wildcards (SPM-CW). Here we consider that a type of wildcard characters “*” is used to represent gaps in the pattern for the first problem of SPM with wildcards. Usually, a wildcard character “*” is used to replace with zero or more letters in the text for the pattern matching problem. Yasuda et al. (ACISP 2014) proposed a protocol with an existing data packing method for secure wildcards pattern matching using symmetric somewhat homomorphic encryption (SwHE) in the semi-honest model in which a wildcard character in the pattern is replaced with just one letter in the text. Furthermore, we enhance their work to replace a wildcard with any sequence of letters in the text then propose SPM-RW protocols by using the symmetric and public-key SwHE schemes in the semi-honest model. Also, we propose a packing method that improves the number of homomorphic multiplications by a factor of k compared to a naive usage of Yasuda et al.’s method to solve the SPM-RW problem in which k is the number of sub-patterns. Next, we consider the SPM-CW problem for processing private database queries, which allows a few types of wildcards (“$”, “*”, and “!”) to appear in the pattern. To solve this problem, we propose an SPM-CW protocol using a double-query technique with public-key SwHE encryption in the semi-honest model. Our experiments exhibit the practicality of the new protocols for SPM-RW and SPM-CW, which outperforms state-of-the-art.

ジャーナルJournal of Information Security and Applications
出版ステータスPublished - 2020 12月

ASJC Scopus subject areas

  • ソフトウェア
  • 安全性、リスク、信頼性、品質管理
  • コンピュータ ネットワークおよび通信


「Efficient protocols for private wildcards pattern matching」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。