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