Cloud computing provides on demand remote storage and computation resources at a cost that depends only on the usage rate. However, the loss of the physical control over data and computation raises new challenges in terms of security. These challenges include maintaining privacy of remotely stored data and verification of outsourced computation.
In this talk, we first address the problem of privacy-preserving access to data stored with a cloud provider. Storing the data in encrypted form is a key component in maintaining the privacy of the data. However, encrypting the data is not enough since information about the data may be leaked through the pattern in which users access the data. We show how to achieve efficient privacy-preserving data access using low communication and storage overhead. Our method is based on a combination of encryption, which directly hides data values, and stateless oblivious RAM simulation, which hides the pattern of data accesses. We provide experimental results from our approach and compare it with a more powerful scheme where a client is allowed to keep a state.
In the second part of the talk, we consider the problem of verification of a very common and computationally intensive outsourced computation: keyword search over a document collection. We present a method that allows a client to verify that the result she receives to her query is complete and sound. We propose a solution that requires the cloud provider to compute not only the result, but also a cryptographic proof of the computation. The client then uses the proof to verify that the list of documents returned is correct w.r.t. her query and document collection. We show that our solution adds a small overhead: the size of the proof is as large as the query result, and the verification time for the client is negligible and takes milliseconds.[Abstract]