Paper 2011/434

An Efficient Protocol for Oblivious DFA Evaluation and Applications

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


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. to be appeared in CT-RSA 2012
secure computationsecure pattern matching
Contact author(s)
pmohasse @ cpsc ucalgary ca
2011-11-14: last of 4 revisions
2011-08-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Payman Mohassel and Salman Niksefat and Saeed Sadeghian and Babak Sadeghiyan},
      title = {An Efficient Protocol for Oblivious DFA Evaluation and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2011/434},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.