Source-linked AI summary
Privacy-Preserving Group Data Access via Stateless Oblivious RAM Simulation
Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, Roberto Tamassia
TL;DR
The paper asks how trusted users can privately access data stored with an honest-but-curious outsourced repository when encryption alone leaves access patterns exposed. It combines probabilistic encryption with stateless oblivious RAM simulation, achieving O(log n) amortized overhead with O(n^ν) private workspace and offering an O(log^2 n) alternative without pseudorandom functions.
Problem
Outsourced encryption hides data values but does not by itself hide access patterns that may reveal sensitive information.
Method
The paper combines probabilistic encryption with stateless oblivious RAM simulation using a hierarchy of cuckoo hash tables sharing a common stash.
Results
O(log n) amortized time overhead and O(1) space overhead are achieved with pseudorandom hash functions and O(n^ν) private scratch space; removing those functions raises overhead to O(log^2 n).
Takeaways & Limitations
The scheme supports privacy-preserving access by a stateless group of users and is reported to be effective in practice.
Takeaways & Limitations
The protocols assume the repository manager is honest-but-curious, and the experiments do not explore the broader parameter tradeoffs.
Abstract
from arXiv · showhide
We study the problem of providing privacy-preserving access to an outsourced honest-but-curious data repository for a group of trusted users. We show that such privacy-preserving data access is possible using a combination of probabilistic encryption, which directly hides data values, and stateless oblivious RAM simulation, which hides the pattern of data accesses. We give simulations that have only an $O(\log n)$ amortized time overhead for simulating a RAM algorithm, $\cal A$, that has a memory of size $n$, using a scheme that is data-oblivious with very high probability assuming the simulation has access to a private workspace of size $O(n^ν)$, for any given fixed constant $ν>0$. This simulation makes use of pseudorandom hash functions and is based on a novel hierarchy of cuckoo hash tables that all share a common stash. We also provide results from an experimental simulation of this scheme, showing its practicality. In addition, in a result that may be of some theoretical interest, we also show that one can eliminate the dependence on pseudorandom hash functions in our simulation while having the overhead rise to be $O(\log^2 n)$.
1 Introduction
Outsourced encrypted storage protects data contents but can still reveal sensitive information through access patterns. The paper addresses this gap with stateless oblivious RAM simulation for trusted groups sharing outsourced data.
- Privacy motivation: Encrypted contents alone do not prevent sensitive information from being inferred from users’ access patterns.The paper therefore treats access-pattern hiding as a separate privacy objective.
- Privacy motivation: Probabilistic encryption hides plaintext values and makes encryptions of the same plaintext computationally indistinguishable.Users decrypt, optionally modify, and probabilistically re-encrypt each accessed value before returning it to the repository.
- Stateless model: The framework models a trusted group as stateless Alice, whose private cache cannot carry information between access episodes.This captures cooperating users who share access to Bob’s memory but do not communicate outside it.
- Stateless model: Data-oblivious access requires the observed access distribution to depend on memory size, cache size, and sequence length, not input data values.The formal condition states that access-sequence probabilities are identical across equal-sized memory configurations.
- Our results: The paper gives a stateless simulation with O(log n) time overhead and O(1) space overhead using O(n^ν) private scratch space.The access sequence is data-oblivious with very high probability, and the private workspace carries no state between episodes.
- Our results: The construction uses a hierarchy of cuckoo hash tables sharing one O(log n)-size stash and avoids dummy elements.Without pseudorandom functions, the overhead increases to O(log^2 n).
2 Theory Background
Oblivious RAM simulations use hash-table hierarchies to hide access patterns, with cuckoo hashing improving efficiency. The paper develops a shared-stash hierarchy whose stash remains logarithmic with high probability.
- Oblivious RAM simulation: O(log n) levels store n items in a hierarchy of hash tables with geometrically increasing sizes.The hierarchy originates in Goldreich–Ostrovsky’s framework, where each level is twice the size of the previous one.
- Cuckoo hashing: Cuckoo hashing uses two tables and two hash functions, giving each key two possible locations and constant-time lookups.Insertion may move displaced keys between alternate locations and can fail after c log n steps.
- Cuckoo hashing: Theta(1/n^2) is the failure probability for inserting a new key in standard cuckoo hashing, while expected insertion time remains constant.The hidden constant depends on the table-load parameter ϵ.
- Stashes: A stash stores keys that cannot be placed in their hash-table locations, converting table failure into stash overflow.A stash of k keys reduces the nth insertion’s failure probability to O(1/n^(k+2)).
- Shared-stash analysis: The hierarchy’s smallest tables require special treatment because their failure probabilities can remain too large even with constant-sized stashes.If the smallest table has size x, its failure probability is O(1/x^(k+2)).
- Shared-stash analysis: O(log n) total stash size suffices across O(log n) levels with probability at least 1−1/n^γ1 for any constant γ1.The analysis dominates per-level stash requirements by geometrically tailed variables and applies Chernoff bounds; it supports any polynomial number of steps.
3 Simulating a RAM Algorithm Obliviously
The paper presents two stateless oblivious RAM simulations: one using pseudorandom functions and cuckoo tables, and one replacing them with a binary-tree technique. The first achieves O(log n) amortized overhead with very-high-probability obliviousness, while the second achieves O(log^2 n) without pseudorandom functions.
- 3.1 Simulation Using Pseudorandom Functions: The server stores a cache Q, a hierarchy of O(log n) cuckoo tables, and a shared stash S.Q has size O(log n); table sizes double through the hierarchy until reaching n.
- 3.1 Simulation Using Pseudorandom Functions: Each RAM access searches Q, S, and every cuckoo table, continuing with random-looking accesses after finding the requested item.The full traversal prevents the server from distinguishing where the item was found.
- 3.1 Simulation Using Pseudorandom Functions: Rebuilds occur on a fixed schedule, moving encrypted items downward through the hierarchy using oblivious sorting and cuckoo-table construction.The schedule depends on the access-sequence position rather than input values, and the rebuild work uses O(n^ν) private workspace.
- 3.1 Simulation Using Pseudorandom Functions: O(log n) amortized time overhead results from charging constant work per element across the table rebuilds, while server space remains O(n).The simulation uses O(log n) rebuilds per access.
- 3.1 Simulation Using Pseudorandom Functions: With very high probability, the server cannot distinguish actual searches from random accesses because the corresponding cuckoo-table configurations remain valid with very high probability.This establishes data-obliviousness for the pseudorandom-function construction.
- 3.2 Simulation Without Pseudorandom Functions: The pseudorandom-function dependence can be removed by placing a complete binary tree over the RAM cells and searching root-to-leaf paths.This modification yields an amortized O(log^2 n) overhead using O(n^ν) private workspace.
4 Performance
The prototype evaluates a hierarchy of cuckoo hash tables with a shared stash, measuring insertion dynamics and stash overflows across RAM sizes, request counts, and table slack. Results indicate that larger tables reduce failures, while broader tradeoff exploration remains future work.
- Failure behavior: A stash of size s log n is enough to avoid failures for a small constant s.Failures occur when moving elements between tables causes the shared stash to overflow during rebuilding.
- Prototype design: The prototype maintains a cache Q and O(log n) cuckoo hash tables, moving elements upward at geometrically increasing access intervals.Each table uses two hash functions and has size (1 + ϵ)2^i log n; the largest table accommodates n items.
- Prototype design: Hash functions are generated using 64-bit seeds obtained from a SHA256 hash chain.
- Tradeoffs: Larger ϵ, larger stashes, and more allowed moves trade additional space or time for lower insertion and failure costs.The study demonstrates feasibility rather than mapping this broad tradeoff space; finer exploration is left for future work.
- Failure behavior: ϵ = 0.2 produced substantially fewer overflows than ϵ = 0.1, and less than log n stash size avoided overflows completely in the limited experiments.The simulation covered up to 1024K RAM items and varying request counts across 1000 trials.
5 Conclusion
The paper concludes that stateless, privacy-preserving access for trusted groups can be achieved with modest private workspace and high-probability data-oblivious simulation. It reports practical effectiveness, while identifying honest-but-curious and trusted-user assumptions as boundaries for future work.
- Conclusion: The schemes provide privacy-preserving access to outsourced data for a group of trusted users with very high probability.Each user has private workspace of size O(n^ν), used for computation without carrying state between interactions.
- Conclusion: Assuming pseudorandom hash functions, the protocol has O(log n) amortized time overhead and O(1) space overhead.Without pseudorandom hash functions, the overhead rises to O(log^2 n).
- Conclusion: Experimental results indicate that the protocol is effective in practice.
- Future work: The protocols assume that the data repository manager Bob is honest-but-curious.Adapting the schemes to semi-trusted or malicious behavior is posed as future work.
- Future work: The cooperating group members are assumed to be trusted.The paper raises whether schemes can handle members who collude with Bob or reveal other users’ access patterns.