Privacy-Preserving Regular Expression Matching using Nondeterministic Finite Automata

Ning Luo, Chenkai Weng, Jaspal Singh, Gefei Tan, Ruzica Piskac, Mariana RaykovaIACR ePrint 2023

Introduction

Regular expressions (regex) are fundamental to network security, powering critical applications like DNS policy enforcement and Intrusion Detection Systems (IDS). However, these operations often involve sensitive data. For instance, in DNS filtering, a user may wish to prove their query is not on a blocklist without revealing the query itself. Similarly, in intrusion detection, a company might want to scan network traffic against proprietary attack patterns without exposing those patterns to the network provider or accessing the raw traffic.

Standard regex matching is inherently input-dependent, as memory access patterns vary based on the input characters. In privacy-preserving contexts like Secure Multi-Party Computation (MPC), this dependency leaks information. Previous solutions relied on expensive matrix multiplications or oblivious data structures, which often proved too slow for practical deployment. This paper introduces a suite of protocols that transform regex matching into a data-oblivious algorithm, achieving a 4.5X improvement in communication efficiency over previous state-of-the-art methods.

Methodology: Two-Scan TNFA Simulation

The core innovation of this work is the Two-Scan Thompson Nondeterministic Finite Automaton (TNFA) Simulation. The authors observed a unique structural property of TNFAs: any reachable node can be reached via a path containing at most one backward edge.

Thompson NFA structure illustrating the transitions used in the two-scan simulation.

Instead of a standard, non-oblivious Depth-First Search (DFS), the proposed algorithm performs two linear passes over the NFA states. The first pass processes forward edges, while the second pass handles the single possible backward edge. This approach ensures that memory access patterns are entirely independent of the input string, making the algorithm "data-oblivious."

Building on this simulation, the authors developed three distinct protocols:

  1. ZK-regex: A zero-knowledge proof allowing a prover to demonstrate a string matches a public regex without revealing the string itself, utilizing the "MPC-in-the-head" framework.
  2. Secure-regex (OS-based): A constant-round 2PC protocol using an Oblivious Stack, optimized for high-latency wide-area networks (WAN).
  3. Secure-regex (OT-based): A 2PC protocol using Oblivious Transfer that is more communication-efficient for shorter regex patterns, though it requires more rounds.

Evaluation and Key Results

The protocols were evaluated using real-world security datasets, including Pi-hole DNS filtering rules and a filtered set of 416 classical regex patterns from the SNORT PCRE intrusion detection database.

Comparison of communication and round complexity between the proposed protocols and existing state-of-the-art methods.

The results demonstrate significant performance gains. The proposed protocols achieved a 4.5X reduction in communication costs compared to the previous best-known protocol, "ONE" by Sasakawa et al. For a typical DNS query (128-byte string, 97-byte pattern), a zero-knowledge proof can be generated in just 0.57 seconds. Furthermore, the OS-based protocol scales efficiently with regex length, maintaining $O(mn \log n)$ complexity, a marked improvement over the $O(mn^2)$ complexity of prior methods.

Discussion and Future Work

While the current suite of protocols offers substantial improvements, it is limited to "classical" regular expressions (union, concatenation, Kleene star, and wildcards). It does not yet support advanced PCRE features such as backreferences or look-around assertions. Additionally, the 2PC protocols involve a preprocessing phase for generating cryptographic primitives like Beaver triples, which contributes to the total computational overhead. Future research may focus on extending this data-oblivious logic to more complex automata or leveraging hardware acceleration to further enhance performance.

Summary updated

BibTeX
@article{luo2023privacy,
  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}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2023},
}
Figure