Cryptology ePrint Archive: Report 2012/698

5PM: Secure Pattern Matching

Joshua Baron and Karim El Defrawy and Kirill Minkovich and Rafail Ostrovsky and Eric Tressler

Abstract: In this paper we consider the problem of secure pattern matching that allows single-character wildcards and substring matching in the malicious (stand-alone) setting. Our protocol, called 5PM, is executed between two parties: Server, holding a text of length $n$, and Client, holding a pattern of length $m$ to be matched against the text, where our notion of matching is more general and includes non-binary alphabets, non-binary Hamming distance and non-binary substring matching.

5PM is the first secure expressive pattern matching protocol designed to optimize round complexity by carefully specifying the entire protocol round by round. In the malicious model, 5PM requires $O((m+n)k^2)$ bandwidth and $O(m+n)$ encryptions, where $m$ is the pattern length and $n$ is the text length. Further, 5PM can hide pattern size with no asymptotic additional costs in either computation or bandwidth. Finally, 5PM requires only two rounds of communication in the honest-but-curious model and eight rounds in the malicious model. Our techniques reduce pattern matching and generalized Hamming distance problems to a novel linear algebra formulation that allows for generic solutions based on any additively homomorphic encryption. We believe our efficient algebraic techniques are of independent interest.

Category / Keywords: Secure pattern matching, wildcard pattern matching, substring pattern matching, non-binary Hamming distance, secure two-party computation, malicious adversary, full simulation, homomorphic encryption, threshold encryption

Publication Info: Preliminary version at SCN 2012. This is the full version.

Date: received 11 Dec 2012, last revised 1 Jul 2013

Contact author: jwbaron at hrl com

Available format(s): PDF | BibTeX Citation

Version: 20130701:212757 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]