Using Data-Oblivious Algorithms for Private Cloud Storage Access
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Framework converts arbitrary RAM accesses into oblivious cloud storage with concrete costs: O(log^2 n) overhead with constant client registers, O(log n) with n^epsilon local memory, and constant overhead if both local memory and message sizes are n^epsilon. Key tools are cuckoo hashing with a stash of size log n to drive negligible failure probability, a data-oblivious MapReduce and external-memory sorting network to build tables, and specialized oblivious algorithms achieving O(n log n) convex-hull and linear-size WSPD/quad-tree constructions for nearest neighbors.
AI-written summary · about
chapters (17)
- 0:00Privacy in the Cloud
- 1:21Encryption is not sufficient
- 3:20Oblivious Data Storage
- 9:24Cuckoo Hashing Technique
- 9:46Cuckoo Insertion
- 10:35Using a Stash
- 11:29Using a Big Stash
- 11:53MapReduce
- 15:13Our Simulation
- 15:49For each Access to i
- 16:54Cascading
- 17:37Convex Hull Representation
- 18:40Our Approach
- 19:07Merge Step
- 19:19Tangent-Finding Cases
- 21:18Data-Oblivious Nearest Neighbors
- 22:12Quadtree Construction
related talks
15mH2O2RAM: A High-Performance Hierarchical Doubly Oblivious RAM
33mYes, There is an Oblivious RAM Lower Bound!
01h 03mHow I Learned to Stop Worrying and Trust the Cloud
11mStripeless Data Placement for Erasure-Coded In-Memory Storage
23mOblivP2P: An Oblivious Peer-to-Peer Content Sharing System
44mAdvancements in Confidential Computing
25mEgalitarian Computing
15mWeave: Efficient and Expressive Oblivious Analytics at Scale