Efficient and Secure Search over Encrypted Data

Abstract

Due to a variety of crucial bene fits, enterprises outsource their data to cloud resident storage. The outsourced data needs to be stored in encrypted form on remote untrusted servers to preserve privacy. However, if the client has to retrieve the entire data and decrypt it in order to get results for a search query then that will defeat the purpose of outsourcing. A solution to this problem is Searchable Encryption that provides a reasonable trade-off between security and effciency. Our first contribution is in the context of Dynamic Searchable Symmetric Encryption (DSSE). DSSE schemes, apart from providing support for search operation, allows a client to perform update operations on outsourced database efficiently. Two security properties, viz., forward privacy and backward privacy are desirable from a DSSE scheme. The former captures that the newly updated entries cannot be related to previous search queries and the latter ensures that search queries should not leak matching entries after they have been deleted. These security properties are formalized in terms of the information leakage that can be incurred by the respective constructions. Existing backward private constructions either have a non- optimal communication overhead or they make use of heavy cryptographic primitives. This work makes two contributions: (i) propose alternative formulations of information leakage for backward privacy after revisiting the existing ones [Bost et al. CCS'17], (ii) construct three efficient backward private schemes that aim to achieve practical efficiency by using light weight symmetric cryptographic components only. Our first construction BP-prime achieves a stronger notion of backward privacy whereas our next two constructions BP and WBP achieve optimal communication complexity at the cost of some additional leakage. The prototype implementations of our schemes depict the practicability of the proposed constructions and indicate that the cost of achieving backward privacy over forward privacy is substantially small. Certain applications require some type of fuzzy searches like wildcard and edit-distance based search over encrypted data. In our second work, we investigate the problem of secure wildcard search over encrypted data in Outsourced Symmetric Private Information Retrieval (OSPIR) setting. 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 propose two schemes, viz., BS and OTE to support secure wildcard search over encrypted data. Construction BS reduces the problem of secure wildcard search to that of boolean search. BS is a sub-linear wildcard search protocol but it allows false positives. Our second construction OTE utilizes Oblivious Transfer Extension protocols to obtain linear time wildcard search protocol with no false positives. BS and OTE can then be combined to obtain an efficient sub-linear solution with no false positives. We provide performance analysis based on our prototype implementation to depict the feasibility of our proposed constructions.