5PM: Secure Pattern Matching
Joshua Baron, Karim El Defrawy, Kirill Minkovich, Rafail Ostrovsky, Eric Tressler
Abstract:
In this paper we consider the problem of secure pattern matching that allows single character wildcards ,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 protocol with communication complexity sub-liner in circuit size to compute non-binary substring matching in the malicious model (general MPC has communication complexity which is at least liner in the circuit size). 5PM is also the first sublinear protocol to compute non-binary Hamming distance in the malicious model. Additionally, in the honest-but curious (semi-honest) model, 5PM is asymptotically more efficient than the best known scheme when amortized for applications that require single charcter wildcards or substring pattern matching. 5PM in the malicious model requires o((m+n)k2 ) 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 2 rounds of communication in the honest-but-curious model and round 8 rounds in malicious model. Our techniques reduce pattern matching and generalized Hamming distance problem 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.
comment: Preliminary version appeared in SCN 2012 PP: 222-240. Full version appeared in Journal of Computer Security 21(5): 601-625 (2013)
Fetch PDF file of the paper
| Back to Publications List |