Welcome to the resource topic for 2010/484
Title:
Automata Evaluation and Text Search Protocols with Simulation Based Security
Authors: Rosario Gennaro, Carmit Hazay, Jeffrey S. Sorensen
Abstract: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.
ePrint: https://eprint.iacr.org/2010/484
Talk: https://www.youtube.com/watch?v=r9dQL92bcs4
Slides: http://www.iacr.org/workshops/pkc2010/22_text_search_protocols_with_simulation_based_security/
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .