Secure pattern matching based on bit parallelism: Non-interactive protocols for non-deterministic string matching automata evaluation

In this paper, we consider the problem of secure pattern matching that uses evaluation of non-deterministic string matching automata (NSMA). Our solution is based on a class of hardware-based pattern matching algorithms called bit-parallel pattern matching, which simulates the behavior of NSMAs. The properties of this class of algorithms allow our constructions to handle any fixed-length pattern in a non-interactive way with only two rounds of communication. Our secure protocol is able to handle the Hamming distance computation and substring and subpattern matching for any finite alphabet. It is also possible to use this protocol for keyword, text, and live text search. Security of our protocol is proved in the semi-honest model. Then, in order to strengthen security of the solution and retain its efficiency, we design a variant of the protocol which is proved to be secure with one-sided simulation in the malicious model. As a proof of concept, we also present another protocol that shows how our basic idea can be extended to other scenarios of pattern matching such as secure computation outsourcing.