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) Short URL: ia.cr/2012/698 Discussion forum: Show discussion | Start new discussion