PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Practical Oblivious RAM

Emil Stefanov, Elaine Shi, Dawn Song

arXiv:1106.3652v5cs.CR

TL;DR

Cloud storage can leak sensitive information through access patterns even when data is encrypted, motivating practical oblivious RAM. The paper uses partitioning, optimized partition O-RAMs, and concurrent background work to reduce overhead while preserving obliviousness. It reports 20X–35X amortized overhead for roughly 1-terabyte O-RAMs and a 63-times bandwidth improvement over the best prior scheme, while recursion reduces client storage to a sublinear amount.

  • Problem

    Encrypted cloud storage does not hide access patterns, while existing O-RAM constructions have impractical overhead despite asymptotic guarantees.

  • Method

    The paper partitions a large O-RAM into smaller O-RAMs, uses an optimized partition construction, and performs reshuffling concurrently with reads and writes.

  • Results

    20X–35X amortized overhead is achieved for roughly 1-terabyte O-RAMs, with 63–66 times less bandwidth than the best previously known scheme under identical parameters.

  • Takeaways & Limitations

    Partitioning and background eviction provide the key technique for making O-RAM practical while also supporting the paper’s theoretical bounds.

  • Takeaways & Limitations

    The practical construction requires asymptotically linear client-side storage for its linear-size position map, although its constant is small in realistic settings.

Abstract

from arXiv · show

We take an important step forward in making Oblivious RAM (O-RAM) practical. We propose an O-RAM construction achieving an amortized overhead of 20X-35X (for an O-RAM roughly 1 terabyte in size), about 63 times faster than the best existing scheme. On the theoretic front, we propose a fundamentally novel technique for constructing Oblivious RAMs: specifically, we partition a bigger O-RAM into smaller O-RAMs, and employ a background eviction technique to obliviously evict blocks from the client-side cache into a randomly assigned server-side partition. This novel technique is the key to achieving the gains in practical performance.

1 Introduction

Oblivious RAM hides storage access patterns, but existing constructions remain impractical despite strong asymptotic guarantees. This paper proposes partitioning and practical and theoretical constructions that substantially reduce overhead while preserving obliviousness.

  • Motivation: Encrypted storage alone can leak sensitive information through observable data access patterns.A sequence of requests followed by a stock exchange operation could reveal information even when the data is encrypted.
  • Motivation: More than 1,400X overhead over non-oblivious storage made a leading existing scheme prohibitive in practice.The Goodrich–Mitzenmacher construction had the best asymptotic performance among known constructions, but its practical performance remained unsatisfactory.
  • Main Technique: Partitioning: Partitioning divides one O-RAM into multiple smaller O-RAMs, enabling more efficient handling of partition operations.The framework partitions the server storage into fully functional O-RAMs, with blocks randomly assigned to partitions.
  • Main Technique: Partitioning: Local reshuffling in smaller partitions avoids expensive remote oblivious sorting and supports lower worst-case cost.Concurrent reshuffling and reads further reduce the practical construction’s worst-case cost to O(log N).
  • Main Technique: Partitioning: The construction must make the sequence of accessed partitions appear pseudorandom so partitioning does not reveal block identities.Partitioning introduces an additional channel through which access patterns could otherwise be inferred.

2 Problem Definition

The problem is to outsource data to an untrusted server while hiding which blocks are accessed and how requests are patterned. O-RAM addresses this through randomized server-side access, while practical design must account for bandwidth and latency constraints.

  • System Model: A client can outsource data to an untrusted server while retaining trusted CPU and memory resources.The setting stores N blocks of B bytes at the remote server.
  • Security Goal: O-RAM aims to make each request generate a random-looking server access sequence that reveals no access-pattern information.The protected information includes block identity, recency, repeated access, sequentiality, and whether the request is a read or write.
  • Practical Considerations: Bandwidth and latency are expected to be the main practical bottlenecks in realistic cloud deployments.The paper contrasts expensive network transfer with relatively abundant client computation and storage.
  • Practical Considerations: The practical construction uses client-side storage as a working buffer to reduce client-server bandwidth consumption.The target scenario involves terabytes of outsourced data and megabytes to gigabytes of client storage.

3 The Partitioning Framework

The partitioning framework divides one O-RAM into smaller, fully functional partition O-RAMs and randomly reassigns accessed blocks among them. Background eviction moves cached blocks independently of requests, making partition accesses reveal no information about the data request sequence while enabling secure construction and practical client storage.

  • Partitioning Framework: Partitioning divides the server storage into P fully functional O-RAMs containing N/P blocks on average, while hiding access patterns within each partition.Each partition can be treated as a black-box O-RAM exporting read and write operations.
  • Partitioning Framework: Each accessed block is logically removed from its current partition and independently assigned to a fresh random partition, with the position map tracking its location.A stale copy may remain in the former partition, but the position map identifies the current associated partition.
  • Client Storage: The client uses P-slot data cache, a position map, a shuffling buffer, and miscellaneous cryptographic state to manage partitioned storage.The position map records each block’s partition and, in the practical construction, its level and offset; the cache holds temporarily fetched blocks.
  • Partition O-RAM Operations: Every data request performs both a server read and write, including a dummy read on cache hits, because the cache is required for security rather than efficiency.Fetched blocks remain in the client cache until background eviction writes them to a randomly associated server partition.
  • Background Eviction: Background eviction operates independently of data requests at rate ν, writing cached blocks to their associated partitions and using dummy blocks when selected slots are empty.This load-independent process prevents the server from learning which cache slots are filled; piggy-backed evictions are optional and can improve performance by a constant factor.
  • Security: Random partition assignment and request-independent background eviction make partition access sequences independent of data access patterns, yielding security when each partition O-RAM is secure.Any two equal-length data request sequences induce identically distributed partition-number sequences, and the framework preserves security over P secure partition O-RAMs.

4 Practical Construction

The practical construction partitions the O-RAM into smaller components and combines optimized partition storage with background eviction, privacy protections, and authenticated encrypted blocks.

  • Practical construction: 20∼35X amortized overhead is achieved under typical settings, with client storage typically 0.01% to 0.3% of O-RAM capacity.The construction is designed for practical performance and uses partitioning techniques.
  • Practical construction: The construction recursively reduces client storage to O(N) while incurring only a logarithmic factor in amortized cost.
  • Optimized partition O-RAM construction: Partition O-RAMs are optimized through local sorting, eliminating expensive oblivious sorting during reshuffling.Partitions have size O(√N), enabling a client shuffling buffer of size O(√N) for local reshuffling.
  • Optimized partition O-RAM construction: The construction uses a position map instead of Cuckoo hashing and compresses data transfer during reshuffling to obtain practical savings.
  • Partition layout: Blocks are distributed across randomly assigned partitions and levels, with pseudo-random permutations hiding real and dummy block locations from the server.
  • Security: The practical construction provides obliviousness, confidentiality, and authentication with freshness against a malicious server.The client can detect corruption or selective modification of stored or transmitted blocks.

5 Experimental Results

Experiments compare the construction with prior work under matched storage and capacity settings, and examine bandwidth, cache, partition-capacity, and client-storage trade-offs.

  • Experimental setup: The simulations track block locations, client-side storage, and total communication for both the proposed and previously known constructions.Each parametrization simulates exactly 3N read/write operations using a round-robin access pattern that maximizes cache size.
  • Bandwidth and client storage: Bandwidth overhead depends on the background eviction rate, which also determines the client cache size.The experiments define overhead relative to unsecured remote storage and ignore metadata because it is much smaller than block size.
  • Bandwidth and client storage: Figure 9 evaluates how total client storage kNB bytes affects bandwidth overhead, including the cache, sorting buffer, and uncompressed position map.The evaluation assumes a block size of 256 KB.
  • Partition capacity: For large N, the maximum number of real blocks in each partition approaches its expected size, keeping partition capacity less than 5% larger.The construction uses random assignment of blocks and sizes partitions to hide occupancy variation.

6 Reducing the Worst-Case Cost With Concurrency

Concurrency spreads expensive partition reshuffling across time, using an amortizer and concurrent reads to reduce worst-case cost while preserving amortized performance and constant practical latency.

  • Reducing worst-case cost: O(√N) reshuffling costs are spread over time so each time step performs O(log N) work.
  • Amortizer: The amortizer schedules bounded work per time step and allows reads and reshuffling to proceed concurrently.It tracks partitions needing reshuffling and schedules O(log N) work for the practical construction.
  • Results: Concurrent practical construction reduces worst-case cost from O(√N) to O(log N), while recursive construction falls from O(√N) to O((log N)2).
  • Results: Concurrent constructions preserve the amortized cost of their non-concurrent counterparts, while worst-case cost matches amortized cost.
  • Results: The concurrent practical construction retains O(1) latency because each data request requires only a single round-trip.
  • Amortizer: The amortizer processes queued reshuffling jobs in FIFO order, pausing jobs after a bounded amount of work and resuming them later.
  • Results: With probability 1−1/poly(N), the concurrent practical construction has O(log N) worst-case and amortized cost, cN client storage, and O(N) server storage.

7 Recursive Construction

The recursive construction stores the position map in smaller server-side O-RAMs, reducing client storage while adding logarithmic cost factors. A concurrent variant equalizes amortized and worst-case costs.

  • The practical construction is asymptotically limited because its linear-size position map requires a linear fraction of client-side storage.
  • 7.1 Recursive Non-Concurrent Construction: O((log N)^2) amortized cost is achieved by recursively applying the construction, with O(√N) client-side storage and O(N) server-side storage.
  • 7.2 Concurrent Construction: Concurrency reduces the recursive construction’s worst-case cost to O((log N)^2), matching its amortized cost with high probability.
  • Recursion stores the position map in a smaller server-side O-RAM, reducing its client-side representation to O(√N) after repeated capacity reductions.
  • 7.2 Concurrent Reads: Concurrent reads use random dummy positions because these reads are indistinguishable from real reads, avoiding exhausted dummy blocks.

8 Optimizations and Extensions

The paper reduces recursive position-map storage through workload-aware compression and reduces bandwidth by compressing transfers dominated by dummy blocks.

  • 0.255 bytes per block is sufficient for the compressed position map, combining partition-number and level-number encodings.
  • A 1024 TB O-RAM with N = 2^32 blocks has a compressed position map under 1 GB.
  • Sequential access patterns support compressing partition numbers to about 0.13 bytes per block.
  • Level numbers require about 1 bit per block on average because higher levels contain exponentially more blocks.
  • Matrix compression saves a 2X bandwidth factor because at least half of transferred blocks are dummy blocks whose values are irrelevant.

Appendices

The partitioning analysis models blocks as a random process and bounds partition loads under an access-sequence independence assumption.

  • The analysis assumes the data access sequence is independent of the O-RAM scheme’s random coins.
  • Each block is initially assigned to an independent random partition and, after access, is placed into a fresh random partition.
  • At any time, partition loads have the same distribution as randomly throwing N balls into the partitions.
  • With probability 1 − o(1), each partition’s load is bounded by the stated capacity bound at any time.
  • For M ≤ N^k requests, Theorem 8 bounds partition loads over every time step and supports setting each partition’s capacity accordingly.

A.2 Bounding the Client Data Cache Size

The cache analysis models each partition slot as a Markov chain, establishes negative association among slot loads, and derives high-probability total-cache bounds.

  • Background eviction is analyzed alone, yielding an upper bound on client data-cache size because piggy-backed evictions can only reduce it.
  • The expected number of blocks is ρ/(1−ρ) per slot and ρP/(1−ρ) across all cache slots.
  • Negative association enables tail bounds for sums of geometric variables without requiring independence among cache slots.
  • Each slot’s block count plus one is geometrically distributed with mean 1/(1−ρ), and these variables are negatively associated.
  • Starting from empty slots, the data cache never exceeds the theorem’s stated bound with high probability across the request sequence.

B Recursive Construction Costs

The recursive O-RAM construction applies O-RAM* recursively to the position map, yielding logarithmic amortized cost at each stage and quadratic-logarithmic total cost. Its server storage is linear in N, while client storage remains bounded by a square-root term and shared buffers do not asymptotically increase it.

  • O(log N) recursive applications of O-RAM* to the position map produce the recursive O-RAM construction.
  • O(log N) amortized cost for O-RAM* solves to T(N) = O((log N)^2) for the recursive construction.
  • O(N) total server-side storage follows because each partition has capacity O(N) with high probability.
  • O(√N) bounds the client’s data cache with high probability in the O-RAM* construction.
  • A shuffling buffer of size O(N) can be shared across all recursive partitions, so it does not asymptotically increase client-side storage.

C Security of the Practical Partition O-RAM

The practical partition O-RAM hides data-request patterns by making reads pseudo-random without replacement and scheduling reshuffles and writes independently of requests. Reshuffling reveals only that it occurred, while write operations reveal no request-sequence information.

  • ReadPartition avoids rereading a level’s block before that level is reshuffled by moving real blocks to new locations and advancing dummy-block selection.
  • ReadPartition reads server blocks pseudo-randomly without replacement, independently of the data request sequence.
  • A reshuffling of levels leaks no information beyond the occurrence of that reshuffling.
  • WritePartition operations leak no information about the data request sequence.

D Concurrent Constructions: Proof of Worst-Case Cost

The worst-case-cost analysis considers recursive levels up to approximately half the recursion depth, because smaller O-RAM capacities are bounded by O(√N). The recursion then stops and the client stores the remaining level.

  • The analysis focuses on recursion levels 1 ≤ i < 1/2⌊log_α N⌋.
  • At the stopping level, the client simply stores the level.

D.1 Distribution of Amount of Work Queued for One Partition

The queued work for one partition is modeled as an ergodic Markov chain driven by randomized counter advances and deterministic job-generation rules. In steady state, the largest-job distribution yields logarithmic expected work in S, scaled by τ/P.

  • A partition counter advances modulo S when selected by an independent uniform random choice among P partitions.
  • Jobs of size 2^i are enqueued when the counter reaches the corresponding multiple, while existing jobs of size ≤2^i are cancelled and all jobs finish within τ time steps.
  • Queued job sizes are strictly decreasing, and total queued work is at most twice the largest job size.
  • Each partition’s queue is modeled by an ergodic Markov chain whose state records the counter and queued jobs with sizes and ages.
  • π_i = O(τ/(P·2^i)) bounds the steady-state probability that the largest job has size 2^i.
  • 4τP log S bounds expected largest-job size, while 8τP log S bounds expected work for one partition in steady state.

D.2 Bounding Total Amount of Work Queued for All Partitions

The section bounds the total queued work across partitions despite dependence by establishing negative association and applying concentration arguments. It then derives a high-probability per-time-step work schedule that keeps jobs queued for at most τ time.

  • Total queued work: Lemma 10 bounds the total amount of work across all partitions by summing the maximum job sizes Xj.The analysis uses per-partition tail bounds and accounts for the final partition separately.
  • Total queued work: Negative association replaces the independence assumption needed for the concentration analysis of partition workloads.The construction first considers all but one partition and proves the relevant variables are negatively associated.
  • Concentration analysis: The variables Yj,i encode whether partition j has a job size at least 2^i, enabling tail bounds on aggregate workload.Their probabilities are bounded using the corresponding exact-size probabilities, after which negative association supports the concentration step.
  • Concentration analysis: The negative association proof uses independent stationary partition counters for all but one partition and negatively associated indicators for recent partition selections.Monotonicity then transfers negative association to the resulting Yj,i variables.
  • Work scheduling: 16 log S units of work per time step guarantee, with 1 − 1/poly(N) probability, that each job remains queued for at most τ time.The parameter choice is τ = P.
Loading 1106.3652v5…