Weave: Efficient and Expressive Oblivious Analytics at Scale
summary
Weave implements an oblivious MapReduce pipeline that adds 1% sampling to build a histogram, inserts intermediate “vavers” to perform a two‑stage random then balanced shuffle, and pads with fake records so each reducer sees the same load. The system reports a consistent 3x overhead versus insecure Spark but is 4–10× faster than prior oblivious sort/shuffle methods at large scale, scales linearly to tens of millions of records on SGX VMs, and proves security under an IND‑CDJA indistinguishability model.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:01MapReduce basics
- 2:04Access pattern leakage
- 3:31Distribution and order leakage
- 4:55Obliviousness requirements
- 6:18Research question and Viv’s approach
- 7:02Viv’s two-stage shuffle
- 8:28Balanced shuffle with histogram
- 9:51Security and efficiency of Viv’s shuffle
- 11:22Formal security analysis
- 12:29Implementation and evaluation
- 13:13Performance results
- 14:20Scalability comparison
- 14:41Conclusion
related talks
30mUsing Data-Oblivious Algorithms for Private Cloud Storage Access
55mHigh performance Privacy By Design using Matryoshka & Spark
52mDevil in the Haystack
40mKeeping data private in real-time pipelines
28mOblivious Multi-Party Machine Learning on Trusted Processors
26mRevealing the Unseen - Leveraging XAI for Deeper Data Insights
18mLarge-Scale Data Graph: Scale and Optimize Privacy & Security in Offline Data Systems
21mWhen Oblivious is Not: Attacks against OPAM