2013 | Emil Stefanov, Marten van Dijk, Elaine Shi, T-H. Hubert Chan, Christopher Fletcher, Ling Ren, Xiangyao Yu, Srinivas Devadas
Path ORAM is an extremely simple Oblivious RAM (ORAM) protocol with small client storage. It is the most practical ORAM scheme known to date with small client storage. The protocol ensures that the access pattern to remote storage is hidden from the server, making it statistically secure. Path ORAM achieves an asymptotic bandwidth cost of O(log N) for blocks of size B = Ω(log² N) bits. It is asymptotically better than the best known ORAM schemes with small client storage for such block sizes. Path ORAM has been adopted in the design of secure processors and has theoretical and practical impacts. It is simple, efficient, and has been shown to outperform existing ORAM schemes in terms of both asymptotic efficiency and practicality. The protocol uses a binary tree structure for server storage and a stash for client storage. It has been proven that the probability of failure is negligible for reasonable block sizes. Path ORAM is also statistically secure and has been used in various applications, including secure multiparty computation. The protocol's simplicity and efficiency make it a valuable tool in the field of secure computing.Path ORAM is an extremely simple Oblivious RAM (ORAM) protocol with small client storage. It is the most practical ORAM scheme known to date with small client storage. The protocol ensures that the access pattern to remote storage is hidden from the server, making it statistically secure. Path ORAM achieves an asymptotic bandwidth cost of O(log N) for blocks of size B = Ω(log² N) bits. It is asymptotically better than the best known ORAM schemes with small client storage for such block sizes. Path ORAM has been adopted in the design of secure processors and has theoretical and practical impacts. It is simple, efficient, and has been shown to outperform existing ORAM schemes in terms of both asymptotic efficiency and practicality. The protocol uses a binary tree structure for server storage and a stash for client storage. It has been proven that the probability of failure is negligible for reasonable block sizes. Path ORAM is also statistically secure and has been used in various applications, including secure multiparty computation. The protocol's simplicity and efficiency make it a valuable tool in the field of secure computing.