View article

This paper presents an efficient protocol for securely computing the fundamental problem of pattern matching. This problem is defined in the two-party setting, where party P ₁ holds a pattern and party P ₂ holds a text. The goal of P ₁ is to learn where the pattern appears in the text, without revealing it to P ₂ or learning anything else about P ₂’s text. Our protocol is the first to address this problem with full security in the face of malicious adversaries. The construction is based on a novel protocol for secure oblivious automata evaluation which is of independent interest. In this problem party P ₁ holds an automaton and party P ₂ holds an input string, and they need to decide if the automaton accepts the input, without learning anything else.