Path ORAM: An Extremely Simple Oblivious RAM Protocol

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 = Omega(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 in corpus (16)

• Privacy-Preserving Shortest Path Computation
• Deterministic, Stash-Free Write-Only ORAM
• MI6: Secure Enclaves in a Speculative Out-of-Order Processor
• TensorTEE: Unifying Heterogeneous TEE Granularity for Efficient Secure Collaborative Tensor Computing
• Preventing Your Faults From Telling Your Secrets: Defenses Against Pigeonhole Attacks
• Visor: Privacy-Preserving Video Analytics as a Cloud Service
• Obladi: Oblivious Serializable Transactions in the Cloud
• The Melbourne Shuffle: Improving Oblivious Storage in the Cloud
• BliMe: Verifiably Secure Outsourced Computation with Hardware-Enforced Taint Tracking
• SoK: Cryptographically Protected Database Search
• BIOS ORAM: Improved Privacy-Preserving Data Access for Parameterized Outsourced Storage
• Fair Marketplace for Secure Outsourced Computations
• More is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting
• Optimizing Path ORAM for Cloud Storage Applications
• Strongly Secure and Efficient Data Shuffle On Hardware Enclaves
• Oblivious Sorting and Queues