Paper 2012/698

5PM: Secure Pattern Matching

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


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.

Available format(s)
Publication info
Published elsewhere. Preliminary version at SCN 2012. This is the full version.
Secure pattern matchingwildcard pattern matchingsubstring pattern matchingnon-binary Hamming distancesecure two-party computationmalicious adversaryfull simulationhomomorphic encryptionthreshold encryption
Contact author(s)
jwbaron @ hrl com
2013-07-01: last of 2 revisions
2012-12-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joshua Baron and Karim El Defrawy and Kirill Minkovich and Rafail Ostrovsky and Eric Tressler},
      title = {5PM: Secure Pattern Matching},
      howpublished = {Cryptology ePrint Archive, Paper 2012/698},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.