Cryptographic Hardness of Correlated Sampling
summary
Shows that converting perfect generalization (or stability) into replicability hinges on correlated sampling and cryptography: a white box correlated sampling routine would collapse statistical zero knowledge into differential privacy, so assuming Rabin public-key encryption is secure there is no efficient uniform conversion, while absence of one-way functions gives an average-case construction and absence of auxiliary-input one-way functions gives a worst-case construction. Tools include shift-and-round, hashing plus rejection sampling, and reductions to SZK; constructions work information theoretically but fail under standard cryptographic hardness.
AI-written summary · about
chapters (9)
- 0:00Start
- 8:06Is replicability achievable?
- 10:26Randomized Rounding for Replicability
- 21:23Example
- 22:29Statistical zero knowledge
- 23:19Necessity of cryptographic assumptions
- 24:59Warm-up
- 27:22General case, attempt 1: problems
- 28:08Open problems
related talks
41mReducibility and Statistical-Computational Gaps from Secret Leakage
28mSample-based Proofs of Proximity
01h 03mSecure Computation 2
20mOn the computational hardness needed for quantum cryptography
46mCryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
01h 10mSecure Multiparty Computation II
40mA Duality Between One-Way Functions and Average-Case Symmetry of Information
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics