With the emergence of cloud computing, outsourcing data services to cloud servers is becoming more and more prevalent. Along with this arise also security and privacy concerns. Particularly, it is an important concern to the user that the service provider itself may be malicious and breach the secrecy and privacy of users. Although encrypting data content has been a common practice, it does not relieve the concerns, because users data access pattern is not preserved and researchers have found that a wide range of private information could be conveniently revealed by observing the access pattern. It is, therefore, critical to investigate the problem of protecting users access pattern privacy in untrusted storage.

Existing solutions that provide strict protection to the privacy of access pattern incur very high overhead, such as high bandwidth cost, long round-trip delay and/or large user side storage. The high overhead is a major barrier that hampers the adoption of these solutions in practice. Although strict protection of access pattern privacy is attractive, less strict protection, such as protecting the privacy of long-term access pattern, is also very useful in practice. Based on these considerations, we investigate the problem of protecting the long-term access pattern privacy in un-trusted storage and propose two light-weight schemes to preserve the privacy of long-term access pattern. We conduct rigorous proofs and extensive evaluations to demonstrate that the proposed schemes can hide the data access pattern in the long run, and the number of accesses required to preserve the access pattern privacy is reasonable in many situations.

With outsourced data storage, keyword based query is a critical and primitive function for the users to access the data of their interest. Similar to access pattern, exposure of query pattern also leads to the leakage of sensitive information about the queried keyword and data. We show that without proper protection of both the query trapdoor and the access pattern, the query pattern may be exposed readily. Based on the framework of our access pattern privacy protection schemes, we propose a novel defense solution that protects the query privacy in a light-weight manner.

One important benefit offered by cloud storage is its convenience for data sharing among multiple users. But when not all users are trusted, it is important to hold malicious users accountable for their misconduct. Due to conflicting goals of user accountability and access pattern privacy preservation, existing user accountability solutions cannot be readily integrated with ORAM constructions. As the last part of this dissertation, we investigate the problem of introducing support of user accountability into hash-based ORAM.We propose a scheme that can detect misconduct by malicious users and identify the attackers, while not interfering with the access pattern preservation mechanisms inherent from the underlying ORAM. Security and overhead analysis shows that the proposed scheme has achieved the design goals of providing accountability support to ORAM and preservation of data access pattern privacy, at the cost of slightly increased storage, communication, and computational overheads.