Welcome to the resource topic for 2023/643
Title:
Privacy-Preserving Regular Expression Matching using Nondeterministic Finite Automata
Authors: Ning Luo, Chenkai Weng, Jaspal Singh, Gefei Tan, Ruzica Piskac, Mariana Raykova
Abstract: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.
ePrint: https://eprint.iacr.org/2023/643
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .