Path ORAM: Hiding Memory Access
Study the Path ORAM construction — binary trees, stash, and position map — and its security guarantees.
Path ORAM Introduction
Path ORAM, proposed by Stefanov, van Dijk, Shi, Fletcher, Ren, Yu, and Devadas (2013), is the most practically influential ORAM construction. It organizes server storage as a binary tree of buckets, with each leaf corresponding to a position for a data block. Path ORAM achieves O(log^2 N) communication overhead per access in its basic form and is simple enough to implement in a few hundred lines of code.
The Position Map
The position map is a client-side data structure that maps each logical block address to a leaf node in the binary tree. For a database of N blocks with a tree of height L = log N, the position map is an array of N leaf indices. Before accessing block b, the client looks up its current assigned leaf in the position map and assigns it a new random leaf. The old leaf path will be read from and written back to the server.
All lessons in this course
- The Access Pattern Leakage Threat
- Path ORAM: Hiding Memory Access
- Circuit ORAM and Practical Performance
- ORAM in Cloud Storage and Secure Processors