Statistical zero-knowledge

The class of decision problems for which a “yes” answer can be verified by a statistical zero-knowledge proof protocol. In such an interactive proof (see IP), we have a probabilistic polynomial-time verifier, and a prover who has unbounded computational resources. By exchanging messages with the prover, the verifier must become convinced (with high probability) that the answer is “yes,” without learning anything else about the problem (statistically).

See the complexity zoo entry here.

Known relationships

• Graph non-isomorphism has a perfect zero-knowledge proof, so it lies in SZK — GMW91
• SZK is closed under complement (SZK = coSZK) — Oka96 for honest verifiers, GSV98; simpler proof in SV03
• SZK ⊆ AM ∩ coAM — AH91 (AM), For87 (coAM); in particular SZK does not contain NP-complete problems unless PH collapses — BHZ87
• Average-case-hard SZK implies OWFs: if some problem in SZK is hard on average over an efficiently samplable distribution, then one-way functions exist — Ost91
  • From worst-case hardness alone (SZK ⊄ BPP), auxiliary-input one-way functions exist — OW93
• Statistical Difference is SZK-complete — SV03, GSV98

Honest-verifier SZK

$\mathbf{HVSZK}$ is the class of problems with an interactive proof that is statistically zero-knowledge against the honest verifier only: the simulator need only reproduce the view of the verifier that follows the protocol — GSV98.

coSZK

$\mathbf{coSZK}$ is the class of complements of problems in SZK — Oka96.

Statistical Difference

${\mathrm{SD}}^{\alpha ,\beta }$ is the promise problem whose instances are pairs of circuits $(C_0,C_1)$ sampling distributions $D_0,D_1$, with yes-instances $\Vert D_0-D_1{\Vert }_{\mathrm{TV}}\ge \alpha$ and no-instances $\Vert D_0-D_1{\Vert }_{\mathrm{TV}}\le \beta$. Statistical Difference $\mathrm{SD}$ is ${\mathrm{SD}}^{2/3,1/3}$. For constants ${\alpha }^2>\beta$, polarization reduces ${\mathrm{SD}}^{\alpha ,\beta }$ to it — SV03.

Average-case hardness

$\mathbf{SZK}$ is hard on average if there are a promise problem $\Pi =({\Pi }_Y,{\Pi }_N)\in \mathbf{SZK}$ and a PPT sampler $D$ with $D(1^n)\in {\Pi }_Y\cup {\Pi }_N$ such that for all efficient $\mathcal{A}$,

$$\underset{x\leftarrow D(1^n)}{\mathrm{Pr}}\left[\mathcal{A}(x)=\Pi (x)\right]\le \frac{1}{2}+\mathrm{negl}(n),$$

where $\Pi (x)=1$ if $x\in {\Pi }_Y$ and $\Pi (x)=0$ if $x\in {\Pi }_N$, and the probability is also over the coins of $\mathcal{A}$ — standard.

Participates in

Builds on Statistical zero-knowledge

• SZK = coSZK (via coSZK)
• HVSZK = SZK (via Honest-verifier SZK)
• Statistical Difference is SZK-complete (via Statistical Difference)
• Average-case-hard SZK ⇒ OWF (via Average-case hardness)
• SZK ⊆ AM
• SZK ⊆ coAM
• SZK ⊆ CZK
• SZK ⊆ IP
• SZK ⊆ QSZK

Produces Statistical zero-knowledge

• SZK = coSZK
• DLOG ∈ SZK
• log n)
• HVSZK = SZK
• QR ∈ SZK
• Statistical Difference is SZK-complete

Barriers

• No fully-black-box reduction from iO + OWP to average-case-hard SZK (via Average-case hardness)