Paper 2010/484

Automata Evaluation and Text Search Protocols with Simulation Based Security

Rosario Gennaro, Carmit Hazay, and Jeffrey S. Sorensen


This paper presents efficient protocols for securely computing the following two problems: 1) The fundamental problem of pattern matching. This problem is defined in the two-party setting, where party $P_1$ holds a pattern and party $P_2$ holds a text. The goal of $P_1$ is to learn where the pattern appears in the text, without revealing it to $P_2$ or learning anything else about $P_2$'s text. This problem has been widely studied for decades due to its broad applicability. We present several protocols for several notions of security. We further generalize one of our solutions to solve additional pattern matching related problems of interest. 2) Our construction from above, in the malicious case, is based on a novel protocol for secure oblivious automata evaluation which is of independent interest. In this problem, party $P_1$ holds an automaton and party $P_2$ holds an input string, and they need to decide if the automaton accepts the input, without learning anything else. Our protocol obtains full security in the face of malicious adversaries.

Available format(s)
Publication info
Published elsewhere. Full version of a PKC 2010 paper
secure two-party computationefficient protocolsfull simulation-based securitytext search
Contact author(s)
carmit hazay @ gmail com
2014-08-06: last of 2 revisions
2010-09-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rosario Gennaro and Carmit Hazay and Jeffrey S.  Sorensen},
      title = {Automata Evaluation and Text Search Protocols with Simulation Based Security},
      howpublished = {Cryptology ePrint Archive, Paper 2010/484},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.