An Efficient Secure Two-Party Approximate Pattern Matching Protocol

Approximate pattern matching (APM) is the most suitable for practical applications among the variants of pattern matching, whose function is to determine whether the Hamming distance between two strings is less than a given threshold value. Due to its practicality, APM has a wide range of applications in face recognition, gene matching, etc. However, owing to the sensitivity of private data, data owners are often reluctant to share their private data. Fortunately, secure approximate pattern matching (SAPM) can accomplish the matching function without revealing the data. In this paper, we propose a secure and practical approximate pattern matching protocol based on oblivious transfer (OT), homomorphic encryption (HE), oblivious polynomial evaluation (OPE) and private equality test (PEQT) for the first time, and demonstrate that the protocol has semi-honest adversary security through ideal/realistic simulation paradigm. In terms of efficiency, compared with currently available secure approximate pattern matching works, our protocol has an advantage in the aspect of computation complexity by reducing the complexity from O(nm) to O(nτ), where n is the text length, m is the pattern length, and τ is a given threshold value. Finally, to examine the efficiency, we evaluate the performance of the protocol. The performance result shows that the protocol takes only 10 s to run when the pattern length is 2\+6 and the text length is 2\+\{12\}.