Welcome to the resource topic for 2011/434
Title:
An Efficient Protocol for Oblivious DFA Evaluation and Applications
Authors: Payman Mohassel, Salman Niksefat, Saeed Sadeghian, 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.
ePrint: https://eprint.iacr.org/2011/434
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 .