MAGE: Nearly Zero-Cost Virtual Memory for Secure Computation
Talkat 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI '21) · 2021-07-14..07-16·
summary
MAGE implements a planner and runtime that precomputes the memory programming schedule for oblivious secure computation and applies Belady's algorithm plus deterministic prefetching to hide storage latency. Implemented in C++ with support for garbled circuits and CKS, it runs on Azure and scales password reuse detection to 100 million records per party, running 4–5× faster than OS paging on some kernels and up to an order of magnitude faster on joins, approaching in-memory performance.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:21Secure Computation (SC)
- 1:01Application: Password Reuse Detection
- 1:43Potential SC Applications
- 2:55Memory Overhead of Secure Computation
- 3:33Memory Can Be a Bottleneck for SC
- 4:45Key Observation: SC Programs are Oblivious
- 6:15SC Example: Password Reuse Detection
- 9:04MAGE's Workflow
- 9:46Generating a Memory Program
- 10:57What Makes OS Virtual Memory Slow?
- 12:04Additional Challenges
- 12:30Implementation
- 12:46Evaluation
- 13:18Workloads
- 13:58Password Reuse Application
- 14:29Conclusion
