Paper 2023/643

Privacy-Preserving Regular Expression Matching using Nondeterministic Finite Automata

Ning Luo, Northwestern University
Chenkai Weng, Northwestern University
Jaspal Singh, Oregon State University
Gefei Tan, Northwestern University
Ruzica Piskac, Yale University
Mariana Raykova, Google (United States)

Motivated by the privacy requirements in network intrusion detection and DNS policy checking, we have developed a suite of protocols and algorithms for regular expression matching with enhanced privacy: - A new regular expression matching algorithm that is oblivious to the input strings, of which the complexity is only $O(mn)$ where $m$ and $n$ are the length of strings and the regular expression respectively. It is achieved by exploiting the structure of the Thompson nondeterministic automata. - A zero-knowledge proof of regular expression pattern matching in which a prover generates a proof to demonstrate that a public regular expression matches her input string without revealing the string itself. -Two secure-regex protocols that ensure the privacy of both the string and regular expression. The first protocol is based on the oblivious stack and reduces the complexity of the state-of-the-art from $O(mn^2)$ to $O(mn\log n)$. The second protocol relies on the oblivious transfer and performs better empirically when the size of regular expressions is smaller than $2^{12}$. We also evaluated our protocols in the context of encrypted DNS policy checking and intrusion detection and achieved 4.5X improvements over the state-of-the-art. These results also indicate the practicality of our approach in real-world applications.

Available format(s)
Cryptographic protocols
Publication info
regular expression pattern matchingzero knowledge proofsecure multi-party computationNFA
Contact author(s)
ning luo @ northwestern edu
ckweng @ u northwestern edu
singjasp @ oregonstate edu
gefeitan @ u northwestern edu
ruzica piskac @ yale edu
marianar @ google com
2023-05-08: approved
2023-05-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ning Luo and Chenkai Weng and Jaspal Singh and Gefei Tan and Ruzica Piskac and Mariana Raykova},
      title = {Privacy-Preserving Regular Expression Matching using Nondeterministic Finite Automata},
      howpublished = {Cryptology ePrint Archive, Paper 2023/643},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.