Secure Hashing-Based Verifiable Pattern Matching

Fei Chen, Donghong Wang, Ronghua Li, Jianyong Chen, Zhong Ming, Alex X. Liu, Huayi Duan, Cong Wang, Jing Qin

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)


Verifiable pattern matching is the problem of finding a given pattern verifiably from the outsourced textual data, which is resident in an untrusted remote server. This problem has drawn much attention due to a large number of applications. The state-of-the-art method for this problem suffers from low efficiency. To enable fast verifiable pattern matching, we propose a novel scheme in this paper. Our scheme is based on an ordered set accumulator data structure and a newly developed verifiable suffix array structure, which only involves fast cryptographic hash computations. Our scheme also supports fast multiple-occurrence pattern matching. A striking feature of our proposed scheme is that our scheme works even with no secret keys, which ensures public verifiability. We conduct extensive experiments to evaluate the proposed scheme using Java. The results show that our scheme is orders of magnitude faster than the state-of-the-art work. Specifically, our scheme with public verifiability only costs a preprocessing time of 47 s (merely one-time off-line cost during outsourcing), a search time of 30μ s , a verification time of 149∼mu s , and a proof size of 2760 bytes for a verifiable pattern matching query with pattern length 200 on 10-million long textual data which consists of sequences of two-byte, Unicode characters in Java.

Original languageEnglish
Pages (from-to)2677-2690
Number of pages14
JournalIEEE Transactions on Information Forensics and Security
Issue number11
Publication statusPublished - Nov 2018


  • accumulator
  • hashing
  • Pattern matching outsourcing
  • verifiability

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications


Dive into the research topics of 'Secure Hashing-Based Verifiable Pattern Matching'. Together they form a unique fingerprint.

Cite this