Paper 2011/434

An Efficient Protocol for Oblivious DFA Evaluation and Applications

Payman Mohassel, Salman Niksefat, Saeed Sadeghian, and Babak Sadeghiyan

Abstract

In this paper, we design an efficient protocol for \emph{oblivious DFA evaluation} between an input holder (client) and a DFA holder (server). The protocol runs in a single round, and only requires a small amount of computation by each party. The most efficient version of our protocol only requires $O(k)$ asymmetric operations by either party, where $k$ is the security parameter. Moreover, the client's total computation is only linear in his own input and independent of the size of the DFA. We prove the protocol fully-secure against a \emph{malicious client} and \emph{private} against a malicious server, using the standard \emph{simulation-based} security definitions for secure two-party computation. We show how to transform our construction in order to solve multiple variants of the \emph{secure pattern matching} problem without any computational overhead. The more challenging variant is when parties want to compute the number of occurrences of a pattern in a text (but nothing else). We observe that, for this variant, we need a protocol for counting the number of accepting states visited during the evaluation of a DFA on an input. We then introduce a novel modification to our original protocol in order to solve the counting variant, without any loss in efficiency or security. Finally, we fully implement our protocol and run a series of experiments on a client/server network environment. Our experimental results demonstrate the efficiency of our proposed protocol and, confirm the particularly low computation overhead of the client.

Note: We fixed some minor typos in formal description of the protocol.