Secure Hashing-Based Verifiable Pattern Matching

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

8 Scopus Citations
View graph of relations


  • Fei Chen
  • Donghong Wang
  • Ronghua Li
  • Jianyong Chen
  • Zhong Ming
  • Alex X. Liu
  • Jing Qin

Related Research Unit(s)


Original languageEnglish
Pages (from-to)2677-2690
Journal / PublicationIEEE Transactions on Information Forensics and Security
Issue number11
Online published9 Apr 2018
Publication statusPublished - Nov 2018


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.

Research Area(s)

  • accumulator, hashing, Pattern matching outsourcing, verifiability

Citation Format(s)

Secure Hashing-Based Verifiable Pattern Matching. / Chen, Fei; Wang, Donghong; Li, Ronghua; Chen, Jianyong; Ming, Zhong; Liu, Alex X.; Duan, Huayi; Wang, Cong; Qin, Jing.

In: IEEE Transactions on Information Forensics and Security, Vol. 13, No. 11, 11.2018, p. 2677-2690.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review