Differentially Oblivious Turing Machines
summary
Claim: any multi-tape Turing machine admits a compiler to a Differentially Oblivious Turing Machine that hides any single differing step while incurring only w-logarithmic overhead instead of full ORAM’s logarithmic worst-case blowup. Construction combines a modified Pippenger–Fischer oblivious Turing machine plus a Chen–Xie–Song style differentially private prefix-sum estimator; application to a stack uses periodic DP estimates, O(1) amortized copying and short oblivious windows of size polylog, yielding the stated cost.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 0:10Motivation
- 1:28Oblivious Ram
- 2:28Constructions
- 5:14Differential obliviousness
- 9:53Stable compaction
- 17:54Tools
- 18:43Estimates
- 21:51Algorithm
- 25:26Summary
related talks
28mIndistinguishability Obfuscation for Turing Machines with Unbounded Memory
33mObfuscation with Constant Multiplicative Size Overhead
17mThe Simplest Oblivious Transfer Protocol
20mTaype: A Policy-Agnostic Language for Oblivious Computation
21mWhen Oblivious is Not: Attacks against OPAM
21mWhen Obfuscations Preserve Cryptographic Constant-Time
28mProving Obliviousness of Probabilistic Algorithms with Formal Verification
28mOblivious Multi-Party Machine Learning on Trusted Processors