Cryptology ePrint Archive: Report 2011/434

An Efficient Protocol for Oblivious DFA Evaluation and Applications

Payman Mohassel and Salman Niksefat and 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.

Category / Keywords: cryptographic protocols / secure computation, secure pattern matching

Publication Info: to be appeared in CT-RSA 2012

Date: received 11 Aug 2011, last revised 14 Nov 2011

Contact author: pmohasse at cpsc ucalgary ca

Available format(s): PDF | BibTeX Citation

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

Version: 20111114:193807 (All versions of this report)

Short URL: ia.cr/2011/434