Source-linked AI summary
Oblivious RAM Simulation with Efficient Worst-Case Access Overhead
Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, Roberto Tamassia
TL;DR
Oblivious RAM protects cloud-stored data by hiding access patterns, but existing methods can have large worst-case overhead despite efficient amortized costs. This paper de-amortizes two oblivious RAM simulations, achieving bounded sublinear overhead on every request, including O(log n) for its hierarchical method.
Problem
Existing oblivious RAM solutions hide access patterns but can still incur worst-case overhead as high as Ω(n), limiting their suitability for practical scenarios.
Method
The paper de-amortizes the square-root and log n hierarchical oblivious RAM simulations to make their access overhead worst-case bounded.
Results
The methods achieve sublinear worst-case overhead on every request, including O(√n log2 n) for the square-root method and O(log n) for the hierarchical method.
Takeaways & Limitations
The de-amortized methods make worst-case access overhead asymptotically equal to the corresponding amortized overhead, with the hierarchical solution incurring log n overhead on every request.
Takeaways & Limitations
The security model assumes Bob is honest-but-curious and correctly performs operations without tampering with the data.
Abstract
from arXiv · showhide
Oblivious RAM simulation is a method for achieving confidentiality and privacy in cloud computing environments. It involves obscuring the access patterns to a remote storage so that the manager of that storage cannot infer information about its contents. Existing solutions typically involve small amortized overheads for achieving this goal, but nevertheless involve potentially huge variations in access times, depending on when they occur. In this paper, we show how to de-amortize oblivious RAM simulations, so that each access takes a worst-case bounded amount of time.
1 Introduction
ORAM hides remote data-access patterns because encryption alone does not prevent leakage from access behavior. This paper addresses the remaining worst-case overhead problem by de-amortizing two ORAM constructions.
- Encryption alone does not prevent servers from learning information through users’ data-access patterns.
- Existing ORAM solutions can incur Ω(n) worst-case access overhead despite optimizing amortized overhead.
- Prior methods trade off client memory, access overhead, and repository space, with stateless and stateful variants.
- The paper de-amortizes square-root and log n hierarchical ORAM solutions to provide sublinear worst-case overhead on every request.
2 Preliminaries
The paper’s ORAM constructions use encrypted, obliviously accessed repository structures and scheduled rebuilding. It reviews square-root and hierarchical layouts before de-amortizing their rebuild work.
- 2 Preliminaries: The repository supports read, write, and optionally copy operations, while the server is modeled as honest-but-curious.
- 2 Preliminaries: Probabilistic re-encryption prevents the server from distinguishing reads from writes or recognizing repeated accesses to the same item.
- 2.1 Square-Root Solution: The square-root solution stores a √n-item buffer and a pseudorandomly permuted table, rebuilding the table every √n requests.
- 2.1 Square-Root Solution: O(n log2 n) rebuild accesses incurred once every √n requests produce O(√n log2 n) amortized overhead.
- 2.2 log n Hierarchical Solution: The log n hierarchical solution uses a cache, logarithmically many cuckoo hash tables, and a shared stash, with O(log n) amortized overhead and O(nν) client memory.
3 De-amortized ORAM Simulation
The paper de-amortizes two ORAM constructions by incrementally rebuilding tables while serving requests, yielding bounded worst-case overhead per access. The square-root construction achieves O(√n log2 n) overhead, while the hierarchical construction achieves O(log n) overhead under larger client memory.
- 3.1 The Square Root Solution: The square-root layout uses two √n-sized buffers, two n + √n-sized tables, and an n + 2√n workspace for incremental construction.Requests are grouped into epochs of exactly √n requests while the current table serves accesses.
- 3.1 The Square Root Solution: The square-root method splits an O(n log2 n) table rebuild into √n batches of O(√n log2 n) accesses, executing one batch after each request.The rebuilt table is ready by the end of the √n-request epoch.
- 3.1 The Square Root Solution: O(√n log2 n) worst-case access overhead is achieved by de-amortizing the square-root ORAM approach.The construction also uses O(√n) repository space overhead and O(1) client memory.
- 3.1 The Square Root Solution: Each square-root request scans two buffers, accesses one table entry, and performs one rebuild batch, keeping its worst-case overhead at O(√n log2 n).The method maintains correctness by returning the newest copy from the current buffer, previous buffer, or current table.
- 3.2 The log n Hierarchical Solution: The hierarchical construction incrementally rebuilds tables while serving requests through two caches, a stash, and pairs of cuckoo hash tables.Its algorithm is based on the prior log n hierarchical layout and concurrently rebuilds multiple tables.
- 3.2 The log n Hierarchical Solution: O(log n) worst-case access overhead is achieved by the hierarchical method, with O(n) repository space overhead and O(n^τ) client memory.Here n is the number of data items and τ is any fixed positive constant.
4 Conclusion
The paper de-amortizes two oblivious RAM solutions, making each request’s worst-case access overhead asymptotically match the underlying method’s amortized overhead. Its log n hierarchical solution incurs log n overhead on every request.
- The methods de-amortize the square-root and log n hierarchical oblivious RAM solutions.
- Each method achieves worst-case access overhead asymptotically equal to its underlying solution’s amortized access overhead.
- log n access overhead is incurred on every request by the log n hierarchical solution.