An enhancement of privacy-preserving wildcards pattern matching

Tushar Kanti Saha*, Takeshi Koshiba

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)


We consider secure pattern matching for some alphabet set, where gaps are represented by the character ‘*’. Generally, we know that a wildcard character ‘*’ in the pattern is used to replace zero or more letters in the text. Yasuda et al. (ACISP 2014) proposed a new packing method for somewhat homomorphic encryption for handling wildcards pattern where the wildcards replace one letter in the text. We extend the secure pattern matching so that the wildcards are replaced with any sequences. We propose a method for privacy-preserving wildcards pattern matching using somewhat homomorphic encryption in the semi-honest model. At the same time, we also propose another packing method for executing homomorphic operations between plaintext and encrypted wildcards pattern in three homomorphic multiplications rather than 3k multiplications required by Yasuda et al. method to handle k sub-patterns. Moreover, we have been able to improve the communication complexity of Yasuda et al. method by a factor k denoting the total number of sub-patterns appearing in the pattern. In addition, our practical implementation shows that our method is about k-times faster than that of Yasuda et al. Here, we show some applications of our packing method to computing secure Hamming and Euclidean distances.

Original languageEnglish
Title of host publicationFoundations and Practice of Security - 9th International Symposium, FPS 2016, Revised Selected Papers
EditorsJoaquin Garcia-Alfaro, Frederic Cuppens, Nora Cuppens-Boulahia, Lingyu Wang, Nadia Tawbi
PublisherSpringer Verlag
Number of pages16
ISBN (Print)9783319519654
Publication statusPublished - 2017
Externally publishedYes
Event9th International Symposium on Foundations and Practice of Security, FPS 2016 - Quebec, Canada
Duration: 2016 Oct 242016 Oct 26

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10128 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Symposium on Foundations and Practice of Security, FPS 2016


  • Bioinformatics
  • Biometrics
  • Hamming and euclidean distances
  • Pattern matching computation
  • Privacy-preserving
  • Repetitive-wildcards
  • Somewhat homomorphic encryption

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'An enhancement of privacy-preserving wildcards pattern matching'. Together they form a unique fingerprint.

Cite this