| Cloud computing has been an outstanding computing paradigm in the literature. While promising, it also brings a range of security problems that must be adequately addressed. One class of security problem is related to untrusted cloud (i.e., cloud infrastructure vendors and cloud service providers) that might be compromised. While encrypting data outsourced to the cloud can be used to mitigate such threats, it is insufficient to tackle another difficult problem: How can cloud users trust the results which are the outputs of some computing tasks conducted by the clouds ("delegated computation'') on the users' outsourced encrypted data? This problem leads to a general concept of "verifiability'', which has not been investigated sufficiently. This dissertation addresses three problems in this domain, by presenting three families of provably-secure cryptographic protocols.;The first contribution deals with the problem: how to allow secure keyword search on outsourced encrypted data while complying with flexible access control policies, and assure that the cloud faithfully followed the search procedures? We introduces the solution concept of "verifiable attribute-based keyword search'', which enables data owners to grant keyword search capability with respect to access control policies and data users to delegate keyword search to the cloud as long as their attributes satisfy the access control policies, and further allows data users to verify that the cloud faithfully executed the search operations.;The second contribution is to explore the problem: how can cloud users delegate the set intersection operation to the cloud on their outsourced encrypted data sets, and further verify the correctness of the intersection set returned from the cloud? We introduce the novel notion of "verifiable delegated set intersection on outsourced encrypted data'', which is to delegate the set intersection operation to the cloud, while (i) not giving the decryption capability to the cloud, and (ii) being able to hold the misbehaving cloud accountable.;The third contribution concentrates on the problem: How to achieve verifiable SQL queries on outsourced databases? We present an efficient solution to support various SQL queries that include selection, projection, join, and (weighted) aggregation queries? The solution is built on top of two building blocks: an efficient authenticated data structure to support dynamic update on outsourced databases, and newly devised homomorphic linear tag, which can efficiently verify the integrity of query results via aggregation. |
