Privacy and Integrity of Remote Storage and Computation

Olga Ohrimenko
Brown University

Date and Location: Monday, March 4th, 2013, 10:00am – 11:00am @ Stuart Building, Room 113.


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]


Olga Ohrimenko is a Ph.D. candidate in the Department of Computer Science at Brown University working with Professor Roberto Tamassia. Her interests include devising methods that address privacy, integrity and security issues that emerge in the cloud computing environment. Olga received a B.CS. (Hons) degree from The University of Melbourne in 2007 and her M.Sc. degree from Brown University in 2010. She was also an intern at Google, Microsoft Research and IBM Research.