Efficient and secure outsourced approximate pattern matching protocol

Pattern matching is a basic algorithmic problem that identifies the appearance as well as the location of a pattern in a specific text, and one of the most important variants of that, approximate pattern matching, can be used to discern a substring in the text that is similar to the pattern, as long as their differences stay within a certain threshold. It serves as a basic component in many real-world applications, such as facial recognition, DNA matching and music retrieval. Motivated by the newly emerging secure outsourced computing, in this paper we proposed protocols to realize these functionalities in a privacy-preserving manner. Specifically, we constructed exact and approximate matching protocols, and both of them ensure that the party holds the text (with length of n) learns noting about the pattern (with length of m). We composed a novel idea to combine secret sharing scheme with oblivious transfer (OT), such as to transform the secure pattern matching problem into reconstructing of a shared secret, which means that if a shared secret can be correctly reconstructed, it indicates the pattern indeed exists in the text. Our protocol for approximate pattern matching is generated in the cloud-assisted setting, where the reconstruction phase is outsourced to an honest-but-curious cloud server. Using oblivious transfer extension technique, a powerful method to use few integrated OTs to implement large-scale single OTs, our protocol is efficiently constructed. Both of the protocols are secure in semi-honest model, and we present a detailed secure simulation-based proof in this paper.