.png){kind=icon}
.png){kind=icon}
Return
Efficient protocols for private wildcards pattern matching
.png){kind=icon}
OA
AI
DOI：10.1016/j.jisa.2020.102609.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.. compared to a naive usage of Yasuda et al.'s method to solve the SPM-RW problem in which.. 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.
Keywords:
Privacy-preserving
Repetitive wildcards
Compound wildcards
Secure pattern matching
Somewhat homomorphic encryption
Hamming and Euclidean distances
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.7
Papers:
1.9K
Citations:
4.9K
View more organizations