Queryable Encryption for Outsourced Dynamic Data

Abstract

Nowadays, cloud computing and storage services have become crucial in everyone’s life either directly or indirectly. However, data stored in untrusted cloud servers is prone to attacks by the server itself. In case, the client’s data is sensitive or confidential, the outsourced data need to be stored in an encrypted form. But data encryption poses a challenge for querying over the encrypted outsourced data. Queryable encryption (QE) schemes on encrypted data allow clients to request a query over the encrypted data stored in the cloud. This cloud can be either honest-but-curious or malicious. There might be different types of data and different types of queries over them. One of the primary targets of a QE scheme is to keep the data and queries confidential. Moreover, queries should be efficient even for large data with update support. Dynamic Searchable Encryption (DSE) is a queryable encryption that deals with dynamic text data. In a forward private DSE scheme, adding a keyword-document pair does not reveal any information about the previous search result with that keyword. Whereas, a backward private DSE scheme ensures that search queries do not reveal the information about the deleted file identifiers. To be protected from file-injection attacks, a DSE scheme is desired to be forward and backward private. In this thesis, at first we propose a new and efficient DSE scheme Trids, based on an efficient data structure, for cloud data that achieves better security guarantees and improved efficiency compared to popular DSE schemes. Then, we propose a generic publicly verifiable DSE scheme Srica that makes any forward private DSSE scheme verifiable without losing forward privacy. Moreover, we design a forward private DSE scheme Blasu that supports conjunctive keyword search. At the heart of the construction is our proposed data structure called DIA Tree which is an authentication tree that efficiently returns both membership and non-membership proofs. When the data is a graph, we study the secure link prediction that predicts which new interactions between members are most likely to occur in the near future. We use the number of common neighbors for prediction. We present three algorithms for the secure link prediction problem. Finally, we address the problem of computing clustering coefficient securely. The clustering coefficient is a measure of the degree, to which, the nodes in a graph cluster or associate with one another. We design a scheme Gopas to perform the query on an outsourced encrypted appendable graph data. All the above-mentioned proposed schemes are provably secure. Moreover, we implement prototypes of most of the schemes and tested them with real-life data. The implementation results show that the schemes are practical even for a large database.