Paper 2020/422

Pattern Matching on Encrypted Data

Anis Bkakria, Nora Cuppens, and Frédéric Cuppens


Pattern matching is one of the most fundamental and important paradigms in several application domains such as digital forensics, cyber threat intelligence, or genomic and medical data analysis. While it is a straightforward operation when performed on plaintext data, it becomes a challenging task when the privacy of both the analyzed data and the analysis patterns must be preserved. In this paper, we propose new provably correct, secure, and relatively efficient (compared to similar existing schemes) public and private key based constructions that allow arbitrary pattern matching over encrypted data while protecting both the data to be analyzed and the patterns to be matched. That is, except the pattern provider (resp. the data owner), all other involved parties in the proposed constructions will learn nothing about the patterns to be searched (resp. the data to be inspected). Compared to existing solutions, the constructions we propose has some interesting properties: (1) the size of the ciphertext is linear to the size of plaintext and independent of the sizes and the number of the analysis patterns; (2) the sizes of the issued trapdoors are constant on the size of the data to be analyzed; and (3) the search complexity is linear on the size of the data to be inspected and is constant on the sizes of the analysis patterns. The conducted evaluations show that our constructions drastically improve the performance of the most efficient state of the art solution.

Available format(s)
Public-key cryptography
Publication info
Searchable encryptionPattern Matching
Contact author(s)
anis @ bkakria com
2020-11-13: last of 11 revisions
2020-04-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anis Bkakria and Nora Cuppens and Frédéric Cuppens},
      title = {Pattern Matching on Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2020/422},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.