Source-linked AI summary
Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation
Michael T. Goodrich, Michael Mitzenmacher
TL;DR
The paper asks how outsourced data can remain private when encryption alone does not hide access patterns. It combines parallel MapReduce cuckoo hashing and data-oblivious external-memory sorting to build oblivious RAM simulations. The resulting schemes achieve logarithmic or squared-logarithmic amortized overhead with linear server storage and very high probability, subject to stated assumptions and scope boundaries.
Problem
Outsourcing data requires hiding access patterns as well as contents, because encrypted communications can still reveal information through access sequences.
Method
The paper combines a parallel MapReduce cuckoo-hashing algorithm, data-oblivious external-memory sorting, and hash-table hierarchies for oblivious RAM simulation.
Results
O(log n) amortized overhead is achieved with O(n1/r) private memory, while constant-size private memory achieves O(log2 n), with O(n) server storage and very high probability.
Takeaways & Limitations
Small private memory can be leveraged to provide privacy for a much larger outsourced data set through oblivious RAM simulation.
Takeaways & Limitations
The construction relies on random-hash-function assumptions and has a subtle high-probability issue for small hash tables with logarithmic-sized stashes.
Abstract
from arXiv · showhide
Suppose a client, Alice, has outsourced her data to an external storage provider, Bob, because he has capacity for her massive data set, of size n, whereas her private storage is much smaller--say, of size O(n^{1/r}), for some constant r > 1. Alice trusts Bob to maintain her data, but she would like to keep its contents private. She can encrypt her data, of course, but she also wishes to keep her access patterns hidden from Bob as well. We describe schemes for the oblivious RAM simulation problem with a small logarithmic or polylogarithmic amortized increase in access times, with a very high probability of success, while keeping the external storage to be of size O(n). To achieve this, our algorithmic contributions include a parallel MapReduce cuckoo-hashing algorithm and an external-memory dataoblivious sorting algorithm.
1 Introduction
The paper addresses oblivious RAM simulation for clients outsourcing data while hiding both contents and access patterns, achieving low overhead with small private memory and linear server storage.
- Motivation: Encryption protects outsourced data contents but does not hide access patterns, which can reveal sensitive information.The desired access sequence distribution should depend only on data-set size and number of accesses.
- Problem: Oblivious RAM simulation targets data-oblivious access for computations that are not naturally data-oblivious, even when private memory is O(n1/r).The paper considers constant-size private memory and sublinear private memory for constant r > 1.
- Results: O(log n) amortized overhead is achieved with O(n1/r) private memory and O(n) server storage, while constant private memory requires O(log2 n) overhead.Both guarantees hold with very high probability.
- Approach: The approach combines parallel MapReduce cuckoo hashing with deterministic data-oblivious external-memory sorting.These components are used to construct the improved oblivious RAM simulations.
- Assumptions: The construction relies on random-hash-function assumptions, although alternatives without random oracles incur polylogarithmic overhead.The paper treats cryptographic hash functions as making this assumption practical.
2 Preliminaries
The preliminaries review cuckoo hashing, parallel computation models, and data-oblivious sorting, motivating an external-memory oblivious sorter suitable for small internal memories.
- Cuckoo Hashing: Cuckoo hashing stores each key in one of two table locations determined by two hash functions, under total load below 1/2.The standard scheme supports updates while maintaining at most (1 − ϵ)m distinct keys.
- Cuckoo Hashing: The expected insertion time is constant, while the probability that a new key causes failure is Θ(1/n2).These are stated properties of the reviewed cuckoo-hashing scheme.
- Parallel Models: MapReduce expresses parallel computation through map, shuffle, and reduce steps and is presented as a simpler alternative to more general parallel models.The paradigm has been implemented in systems including Hadoop.
- Data-Oblivious Sorting: Data-oblivious external-memory sorting requires an I/O sequence independent of processed data values.Existing efficient external-memory sorts are often non-oblivious, while prior oblivious methods are not sufficiently scalable to very small memories.
- Data-Oblivious Sorting: The paper proposes an external-memory k-way modular mergesort adapted from odd-even mergesort for scalable data-oblivious sorting.Its I/O sequence is data-oblivious and designed for the external-memory setting.
3 MapReduce Cuckoo Hashing
The paper develops a streaming-MapReduce framework and a parallel BFS-based cuckoo-hashing algorithm that processes cuckoo-graph components and provides high-probability efficiency bounds.
- MapReduce Paradigm: Streaming-MapReduce computations use map, shuffle, and reduce phases, with reductions restricted to streaming algorithms using polylogarithmic working storage.Final values are emitted, while non-final values become input to the next map phase.
- MapReduce Paradigm: Message complexity is the total size of all phase inputs and outputs, serving as a work-like performance measure.A ceiling function bounds each phase’s input and output size across executions.
- Cuckoo Graph: The cuckoo graph is bipartite, with edges representing items and endpoints representing their two candidate hash locations.The algorithm uses this graph to organize cuckoo placement.
- Parallel Cuckoo Hashing: Parallel BFS starts from every vertex in U, retaining the search rooted at the smallest item when searches collide.Non-tree edges trigger a reverse cuckoo operation for one edge and stash placement for the others.
- Parallel Cuckoo Hashing: Each connected component is processed in at most three times its size in iterations because BFS waves move down, up, and down.This bounds the per-component processing effort.
- Bounds: O(log n) completion time holds with high probability, while O(n) message complexity holds with very high probability.The time guarantee is sufficient for the oblivious simulation, which does not require very high probability for this component.
4 Simulating a MapReduce Algorithm Obliviously
The paper makes oblivious simulation of sparse-streaming MapReduce efficient by reducing each phase to data-oblivious sorting, yielding a construction for cuckoo hashing and an external-memory sorting primitive.
- Oblivious MapReduce simulation: Data-oblivious sorting is the central primitive used to hide the access sequence during the simulation.The paper explicitly bases the simulation on a reduction to oblivious sorting.
- Oblivious MapReduce simulation: A sparse-streaming MapReduce computation can be simulated data-obliviously in time O(∑_{i=1}^t o-sort(f(i, n))).The bound depends on the ceiling function f for each phase and the data-oblivious sorting time o-sort.
- Oblivious MapReduce simulation: Each phase scans its bounded input, writes map outputs obliviously, sorts key-value pairs by key, and scans the sorted array to perform reduction.Dummy values are emitted for final or dummy inputs, and dummy keys sort after real keys.
- Cuckoo hashing construction: A set of n items can be converted into a size-O(n) two-table cuckoo hash scheme with stash size s in O(o-sort(n + s)) time.The construction applies when the chosen stash size is sufficient.
- External-memory sorting: The external-memory sorting algorithm sorts N items using O((N/B) log^2_{M/B}(N/B)) data-oblivious I/Os under a tall-cache assumption M > 3B^4.Its merge procedure recursively processes sorted arrays, with each recursion level using O(N/B) I/Os.
- Cuckoo hashing construction: With private memory O(n1/r), a two-table cuckoo hashing scheme with stash s = O(log n) can be constructed in O(n + s) time.This result assumes fixed constant r > 1 and that the stash size is sufficient; it combines the cuckoo-hashing and external-sorting theorems.
5 Oblivious RAM Simulations
The simulation uses encrypted, probabilistically re-randomized data arranged in a hierarchy of hash tables, with accesses made data-oblivious through exhaustive and dummy lookups. Cuckoo hashing, stashes, and scheduled rehashing yield logarithmic overhead with linear server storage for both constant and sublinear private memory.
- Privacy model: Probabilistic encryption prevents Bob from correlating stored ciphertexts, leaving Alice’s access sequence as the information requiring protection.The encryption scheme makes repeated encryptions of the same value extremely likely to differ.
- Hierarchical organization: The hierarchy stores real and dummy items in tables H_k through H_L, with capacities 2^i and an initial table H_k accessed exhaustively.Lower-level tables use hashing, while dummy values maintain oblivious access behavior.
- Access phase: Each access searches successive tables, switching to dummy values after finding the requested key, then reinserts the key into H_k without repeating a table lookup.The no-repeat property is central to hiding whether a search found a real item.
- Rebuild phase: Tables are rehashed after geometrically increasing access counts, with padded dummy values and cascaded emptyings preserving obliviousness during rebuilds.When a table’s potential reaches 2^i, its unused values are emptied into the next level; cascades exploit the geometric table sizes.
- Correctness and privacy: With very high probability, searches in cuckoo tables are indistinguishable across found, unfound, and dummy keys because accessed keys form valid hash-table structures.The analysis covers searches for real keys absent from a table, real keys present in it, and dummy keys.
- Performance: O(log^2 n) amortized overhead holds with constant private memory, while O(log n) holds with private memory O(n^{1/r}); server storage is O(n) in both cases.The constant-memory case uses s ∈ O(log n), whereas the sublinear-memory case can use a constant-size stash but requires a different starting level.
6 Conclusion and Future Work
The paper reports improved oblivious RAM simulations for both constant and sublinear private memory. It also identifies hashing without a random oracle and lower-overhead constant-memory simulation as open directions.
- Conclusion: The schemes improve data-oblivious RAM simulation for both constant-memory and sublinear-memory settings.The conclusion characterizes these as efficient schemes with significant improvements in both cases.
- Assumptions and limitations: The analysis assumes suitable completely random hash functions, while avoiding a random oracle may add a significant polylogarithmic hashing overhead.The overhead is significant if hashing cannot be performed entirely in private memory or requires polylogarithmic server accesses per hash.
- Future work: The paper leaves oblivious use of explicit sublinear-space hash functions as future work because it is not yet clear that they can be evaluated obliviously.Such functions may also require significant private memory to store.
- Open problems: Open problems include achieving O(log n) amortized overhead with constant private memory and finding a deterministic external-memory data-oblivious sorting method with the stated I/O bound.These are listed as explicit future questions.
A Proof of Cuckoo Component Size Distribution
The proof bounds the size of a cuckoo-graph component by comparing breadth-first exploration with binomial random variables. A Chernoff bound then gives an exponentially decreasing tail probability.
- Breadth-first exploration: A breadth-first search from a fixed vertex is modeled by variables X_i counting newly explored adjacent edges.Each X_i is stochastically bounded by an independent Bin(n, 1/m) variable Y_i.
- Random-variable comparison: The probability that a component contains at least k vertices is bounded by the probability that the sum of independent binomial variables reaches k.The comparison replaces the dependent exploration variables with independent binomial variables.
- Tail bound: nk/m = k/(1 + ϵ), enabling a standard Chernoff bound when ϵ ≤ 1.The stated relation supplies the binomial mean used in the tail calculation.
- Tail bound: β = e^(-ϵ^2/(3(1+ϵ))) gives the resulting exponential decay parameter.The proof defines β from the Chernoff-bound exponent.
B Proof of Data-Oblivious Cuckoo Hashing Theorem
The theorem’s construction converts a data-oblivious MapReduce cuckoo-hashing output into standard table and stash formats. It uses oblivious sorting and scans to place values into their target locations.
- Construction output: A data-oblivious MapReduce cuckoo-hashing construction produces a set S of location–value pairs rather than a table.The conversion begins from the output guaranteed by combining the earlier theorem and lemma.
- Oblivious conversion: The conversion creates tuples for source pairs and target table positions, then data-obliviously sorts them by their coordinates.The tuples distinguish source entries from target locations using markers such as S and T.
- Oblivious conversion: A left-to-right scan copies each source value to its successor target tuple, after which sorting by the second coordinate groups the target assignments.The list is truncated to retain only target tuples before table placement.
- Table formation: The final scan assigns H[i] from each target tuple and yields a standard cuckoo-hash table together with its stash.Unassigned positions receive 0 when no corresponding source tuple is present.
C Proof of Bounds on Cuckoo Hashing when the Stash is Larger than Constant Size
This section generalizes cuckoo-hashing bounds to stashes larger than constant size, establishing high-probability guarantees when table sizes are polylogarithmic in n. It motivates these bounds for the paper’s RAM simulation and identifies a remaining opportunity to improve stash analysis.
- The paper generalizes prior cuckoo-hashing bounds to stashes larger than constant size, which its results require.
- Stashes of size O(log n) are required when each cuckoo subtable has polylogarithmic size m.
- For polylogarithmic m, the probability that a component’s excess reaches j + 1 is at most m^-1−αj for a constant α.
- The derivation requires m to be polylogarithmic in n and uses a bad-event tail analysis to obtain the stated high-probability bounds.
- The analysis bounds the probability that the total stash exceeds s, with s taken as Θ(log n), using the preceding component-excess estimates.
- The authors note that better bounds for larger stashes could simplify the construction, including use of cuckoo tables from the outset with constant private memory.
- A suitably sized stash must support both stored data items and real-or-dummy search locations to preserve the simulation’s very high probability of success.
D A Flaw in the Construction of Pinkas and Reinman
This section identifies a flaw in the Pinkas–Reinman constant-memory construction: lookup patterns for absent items can reveal information about Alice’s access sequence. The paper’s construction avoids this issue by accounting for the validity of dummy as well as real searches.
- Pinkas and Reinman claimed O(log^2 n) expected amortized overhead with O(n) outsourced storage for constant private memory.
- Their construction uses a hierarchy of O(log n) cuckoo hash tables without stashes, doubling in size across levels.
- When previously unaccessed items remain on the bottom level, higher-level lookups may produce locations that cannot correspond to items contained in those tables.
- Such invalid lookup sets can reveal that Alice searched for an item absent from a smaller table, making the access sequence distinguishable.
- The authors report that Pinkas and Reinman planned to repair this flaw in a journal version.