Zero-Knowledge Proofs
Stub. Proving a statement is true while revealing nothing beyond its truth: the foundational interactive zero-knowledge proof systems (Goldwasser-Micali-Rackoff) and the result that every NP statement has one (Goldreich-Micali-Wigderson), then the statistical (information-theoretic, rather than merely computational) variant — its complete problem, and sharp results on statistical difference beyond the "easy" polarizing regime.
Corresponds to CS/ECE 598DA, Weeks 7–8. A zero-knowledge proof lets a prover convince a verifier that a statement is true (e.g. “I know a witness to this NP statement”) without revealing anything else, even the witness itself — formalized by Goldwasser-Micali-Rackoff via the simulation paradigm (whatever the verifier learns, it could have simulated on its own). Goldreich-Micali-Wigderson’s result that every NP statement has a (computational) zero-knowledge proof, assuming one-way functions exist, is what makes ZK a general-purpose cryptographic tool rather than a curiosity. Statistical zero-knowledge (SZK) strengthens the simulation requirement to hold information-theoretically rather than only against efficient verifiers, which shrinks the class of statements provable this way; the class has its own complete problem (statistical difference), and recent work sharpens exactly how hard statistical difference is to estimate outside the regime where simple polarization arguments work.
Outline (TODO — flesh out each)
- Interactive proof systems; the simulation paradigm (Goldwasser-Micali-Rackoff)
- Zero-knowledge proofs for all of NP (Goldreich-Micali-Wigderson)
- Statistical zero-knowledge (SZK)
- The complete problem for SZK (statistical difference)
- Statistical difference beyond the polarizing regime