Oblivious RAM I
summary
Describes why encrypted memory leaks via access patterns in SGX and cloud settings then gives concrete ORAM constructions, costs, and implementations. Tree ORAM uses bucket size about log N and incurs roughly log^3 N bandwidth in classic recursion while PathORAM packs paths and proves stash exceeds R ~ e^{-R} tail bounds with bucket size O(log N). CircuitORAM targets MPC and achieves Circuit ORAM: ~log N bandwidth for log^2 N blocks, yields ~50× smaller circuits in practice, and is used in ASCEND/GhostRider prototypes and the Oblivium compiler.
AI-written summary · about
chapters (25)
- 0:00Introduction
- 1:12Secure Processor
- 4:57adversarial model
- 6:07context context context
- 8:58side channel
- 10:46Key Observations
- 11:13Linkability
- 11:54Hierarchical RAM
- 12:59Entrybased RAM
- 13:24Storage Outsourcing
- 13:42Upside Down
- 13:56Binary Tree
- 14:44Paths
- 17:56Remaining Problems
- 19:25Random Eviction Strategy
- 24:01Formal Proof
- 26:17Flat Partitioning
- 32:22Bucket Size
- 34:29Pathogram
- 40:11Proof
- 52:47Circular RAM
- 54:33Circuit RAM
- 55:14Naive Method
- 56:18Oblivious Method
- 58:44Broken Method
related talks
35mOblivious RAM for MPC
01h 14mPrivate Information Retrieval and Oblivious RAM
01h 11mPrivate Information Retrieval and Oblivious RAM
28mNew Advances in Secure RAM Computation
16mOblivious Plug&Charge: A Privacy-Preserving EV Charging Scheme based on ORAM
01h 03mBeyond Boolean Circuits in Garbled Circuits
49mSubquadratic SNARGs in the Random Oracle Model
15mMAGE: Nearly Zero-Cost Virtual Memory for Secure Computation