Statistical Difference is SZK-complete

Inclusion · SV03, GSV98

Statement

Statistical Difference ${\mathrm{SD}}^{2/3,1/3}$ has an honest-verifier statistical zero-knowledge proof, and every promise problem with one reduces to it by a Karp reduction — SV03. Since honest-verifier and general statistical zero-knowledge coincide (HVSZK = SZK) — GSV98 — ${\mathrm{SD}}^{2/3,1/3}$ is $\mathbf{SZK}$-complete.

Sketch

Polarization first amplifies the gap, so that yes-instances have statistical distance $1-2^{-k}$ and no-instances $2^{-k}$. The proof system then has the verifier sample $b\stackrel{\$}{\leftarrow }\{0,1\}$ and a sample $y$ from $C_b$; the prover must name $b$, which it can do almost always when the distributions are far apart and with probability about $1/2$ when they are close. The honest verifier learns only $b$, which it already knows — SV03.

Notes

• Completeness of Statistical Difference gives a simpler proof that honest-verifier SZK is closed under complement, hence of SZK = coSZK — SV03, GSV98.