Kolmogorov Complexity Characterizes Statistical Zero Knowledge
summary
Main theorem: for any reasonable promise problem A, A in NISZK iff A RP many-one reduces to RK (with RK using approximation error e(m) ≈ Θ(log^2 m)), and A in SZK iff A has a BPP Boolean-formula reduction to RK; logspace analogues replace RP/BPP by RL/BPL and SD/EA by NC0/branching-program versions. Proof builds reductions from EA/support-size to RK by showing high-entropy circuits output many high-K strings while small-support outputs low-K strings, and uses known SZK completeness and Saks–Santhanam style simulators.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:30Information in a string
- 1:20Kolmogorov Complexity
- 3:36Promise version of K complexity: RK
- 8:31Statistical Zero Knowledge (SZK)
- 10:28Circuits encode distributions
- 11:12Statistical Difference problem
- 12:13Non-interactive Statistical Zero Knowledge (NISZK)
- 12:41Entropy Approximation Problem
- 14:17Support size problem
- 15:01Support Size diagram
- 16:28SZK and meta complexity: Shared history
- 20:23Proof Idea: NISZK upper bound for ARK
- 22:02A characterization for SZK
- 25:34Discussion: Reductions to Exact vs Approximate K complexity
- 26:45Discussion: Potential avenue for attack on NP vs NL
related talks
49mLattice-Based Zero Knowledge and Applications
38mNew Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ...
33mHow to Share an NP Statement or Combiners for Zero-Knowledge Proofs
33mAn Introduction to Zero Knowledge Proofs
01h 13mA Zero-Knowledge PCP Theorem
33mA New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
23mZKBoo: Faster Zero-Knowledge for Boolean Circuits
49mHard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness