Unified RAW Path Oblivious RAM

Oblivious RAM (ORAM) is a cryptographic primitive that conceals memory access patterns to untrusted storage. Its applications include oblivious cloud storage, trusted processors, software protection, secure multi-party computation, and so on. This thesis improves the state-of-the-art Path ORAM in several aspects. On the theoretical side, we improve Path ORAM's memory bandwidth overhead by a factor of O(log logN) when the block size is small. With this improvement, Path ORAM is asymptotically the most ecient ORAM construction with constant or polylogarithmic client storage under any block size. Our technique to achieve this improvement involves using pseudorandom functions to compress the position map, a central component in Path ORAM and other position-based ORAMs. With small block size, managing the position map has huge overhead and is Path ORAM's performance bottleneck. Our technique reduces this overhead. On the practical side, we propose Unified ORAM with a position map lookaside buffer to utilize locality in real-world applications, while preserving access pattern privacy. We also propose a new variant of Path ORAM named RAW Path ORAM, which achieves a constant factor reduction in memory bandwidth and encryption overhead. It also features a much simpler proof for correctness compared with Path ORAM. Combining our techniques results in a roughly 2 improvement in ORAM bandwidth, and over 1.43 speedup on SPEC benchmarks. We also study how to eciently verify the integrity of ORAM. Besides some customized optimizations for Path ORAM and RAW Path ORAM, we present a novel integrity verification scheme that works for any position-based ORAM and achieves an asymptotic reduction in hashing overhead over prior solutions.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2014

Author dc:creator

• Ren, Ling, Ph. D. Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Srinivas Devadas.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/93780

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/93780