Privacy-Preserving Regular Expression Matching Using TNFA

Regular expression (regex) is a powerful tool to efficiently search patterns in text strings. However, it is common when the regex and string are privately held by different parties who are unwilling to reveal sensitive information. In this work, we provide solutions for private regex pattern match. By exploiting the structure of Thompson nondeterministic automata, we design a regex match algorithm with O(mn) complexity where m and n are the length of the string and regex. It is oblivious to the input string and, hence, is friendly to private evaluation. We develop two 2-party regex matching protocols that take input a private string from one party and a private regex from another. The first protocol uses oblivious stack as a building block and reduces the communication complexity of the state-of-the-art secure regex protocols from \(O(mn^2)\) to \(O(mn\log n)\) . The second protocol is based on the oblivious transfer and shows better empirical results for short regex in low-latency networks. We also evaluated our protocols in the context of joint intrusion detection and DNA sequence search. The results indicate one more step toward the practicality of private regex pattern matching in real-world applications.