Secure and efficient wildcard search over encrypted data

Abstract

In this work, we investigate the problem of secure wildcard search over encrypted data. The setting comprises of three entities, viz. the data owner, the server and the client. The data owner outsources the encrypted data to the server, who obliviously services the clients’ queries. We first analyze efficiency and security of two recent proposals from International Journal of Information Security, called, respectively, the Wei–Reiter (WR) and Hu–Han (HH) protocol. We demonstrate that HH protocol is completely insecure while WR is not scalable for the problem of wildcard search over encrypted data. Our main contribution consists of three protocols, viz. Π OXT, Π BS and Π OTE, to support secure wildcard search over encrypted data. Protocols Π OXT and Π BS reduce the problem of secure wildcard search to that of boolean search. The search time in Π OXT and Π BS is sub-linear in the number of keywords. Π OXT and Π BS do not rule out false positives completely, but our experiment results indicate that the false positive rate of both the protocols is very less. Our third protocol Π OTE utilizes Oblivious Transfer Extension protocols to achieve linear time wildcard search with no false positive. Π OXT/Π BS and Π OTE can be easily combined to obtain the first construction that addresses the problem of wildcard search in the three-party setting achieving sub-linear search time with no false positives or false negatives. We provide performance analysis based on our prototype implementations to depict the feasibility of our proposed constructions.