A Complete Problem for Statistical Zero Knowledge
Date/Time:17 Oct 2019 17:00
Venue: S17 #06-11
Speaker: Li Zeyong
A Complete Problem for Statistical Zero Knowledge
This work by Amit Sahai and Salil Vadhan presents the first complete problem for SZK, the class of promise problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called STATISTICAL DIFFERENCE, is to decide whether two efficiently samplable distributions are either statistically close or far apart. This gives a new characterization of SZK that makes no reference to interaction or zero knowledge.
The talk (due to time constraint) will focus on the second half (and arguably the more insightful half) of the completeness theorem, that is, STATISTICAL DIFFERENCE is SZK-hard. It essentially gives a constructive proof that any promise problem possessing a statistical zero-knowledge proof can be reduced to an instance of STATISTICAL DIFFERENCE in polynomial time.
Add to calendar: 
