UC Riverside

Cloud computing allows customers to outsource the burden of data management and benefit from economy of scale, but privacy concerns hinder its growth. Even when the stored data are encrypted, access patterns may leak valuable information. We consider the challenge of providing efficient, privacy-preserving access to data outsourced to an untrusted cloud provider.

As motivation for providing data outsourcing protocols with strong privacy guarantees, we introduce two novel attacks against existing "secure" schemes. The first compromises a protocol based on Shamir's Secret Sharing Algorithm that makes invalid security claims. The second sorts encrypted records by their plaintext query-attribute values, and can be applied to any protocol that supports range queries and returns the precise set of encrypted records needed to satisfy each query.

Oblivious RAM (ORAM) protocols guarantee full access pattern privacy, but even the most efficient ORAMs proposed to date incur large bandwidth costs and high response times. We present two novel ORAM protocols. The first minimizes up-front bandwidth costs and achieves near-optimal response times during bursts of requests, while maintaining total bandwidth costs competitive with the best existing ORAM. The second combines ORAM with Private Information Retrieval (PIR) techniques in order to achieve the lowest total bandwidth cost of any ORAM protocol known to date.

Finally, we introduce a generalized form of ORAM called Tunably-Oblivious Memory, which relaxes ORAM's privacy guarantees to allow a bounded amount of information leakage in exchange for lower bandwidth costs. We propose a novel special-purpose Tunably-Oblivious Memory protocol that achieves bandwidth costs lower than those of the best existing ORAM for suitable workloads, while leaking only a few bits of information per query.