Path ORAM

2018/04/12 by Emil Stefanov, Marten van Dijk, Marten Van Dijk +8 · 7 citations
Computer Science · #Cryptography and Data Security #Complexity and Algorithms in Graphs #Security and Verification in Computing

paper · doi:10.1145/3177872

Abstract

We present Path ORAM, an extremely simple Oblivious RAM protocol with a small amount of client storage. Partly due to its simplicity, Path ORAM is the most practical ORAM scheme known to date with small client storage. We formally prove that Path ORAM has a O (log N ) bandwidth cost for blocks of size B = Ω (log 2 N ) bits. For such block sizes, Path ORAM is asymptotically better than the best-known ORAM schemes with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.

Cited by

• SGX-MR: Regulating Dataflows for Protecting Access Patterns of Data-Intensive SGX Applications
• Towards Privacy-Preserving Range Queries with Secure Learned Spatial Index over Encrypted Data
• IVE: An Accelerator for Single-Server Private Information Retrieval Using Versatile Processing Elements
• Obelix: Mitigating Side-Channels Through Dynamic Obfuscation
• CryptGNN: Enabling Secure Inference for Graph Neural Networks
• BOLT: Bandwidth-Optimized Lightning-Fast Oblivious Map powered by Secure HBM Accelerators
• Secure phasing of private genomes in a trusted execution environment with TX-Phase. [europepmc]

Related

• Path ORAM: An Extremely Simple Oblivious RAM Protocol
• Revisiting Definitional Foundations of Oblivious RAM for Secure Processor Implementations
• Sub-logarithmic Distributed Oblivious RAM with Small Block Size
• Succinct Oblivious RAM
• Flat ORAM: A Simplified Write-Only Oblivious RAM Construction for Secure Processors