Secure Outsourced Pattern Matching based on Bit-Parallelism

Secure outsourcing is essential to growth of cloud usage. There are some protocols allowing any functionality to be outsourced. However, specific constructions are necessary in order to do so in an efficient way. In this paper, we consider the problem of secure outsourced pattern matching. Our solution is based on Bit-Parallel Shift-ADD algorithm. The properties of this insecure algorithm allow our construction to search in an outsourced text, without revealing any non-trivial information to the computing server. We achieve a round optimal protocol that allows us to search for patterns with wildcards and handles the Hamming distance computation. Since the protocol has no leakage to the server, it cannot be optimal considering communication complexity; however, we suggest efficient techniques to achieve communication optimality through outsourcing of decryption as well. The security of our protocol is proved in the semi-honest setting. Then, in order to retain the efficiency of the protocol, we omit the correctness property in the malicious setting and prove that the scheme remains private in the presence of malicious adversaries.