Computational zero-knowledge

Same as SZK, except that now the two distributions are merely required to be computationally indistinguishable by any BPP algorithm; they don’t have to be statistically close. The “two distributions” are

1. the distribution over the verifier’s view of their interaction with the prover, conditioned on the verifier’s random coins, and
2. the distribution over views that the verifier can simulate without the prover’s help.

See the complexity zoo entry here.

Notable problems

• OWF ⇒ CZK

Known relationships

• Unlike SZK, it is not known if CZK is closed under complement
• CZK is now known to share other properties with SZK: the verifier may as well be honest (HVCZK = CZK) and may as well show their coins, and CZK is closed under unions — Vad06
• Assuming OWFs exist, CZK contains NP — GMW91
  • Under the same assumption, $\mathbf{IP}\subseteq \mathbf{CZK}$, so $\mathbf{CZK}=\mathbf{IP}=\mathbf{PSPACE}$ — BGG+90, Sha90; unconditionally only $\mathbf{CZK}\subseteq \mathbf{IP}$ is known — folklore
• Contains SZK — folklore

Limits of zero-knowledge

• OWFs are necessary for non-trivial CZK: if a language outside BPP has a CZK proof system, then auxiliary-input one-way functions exist (CZK ⊄ BPP ⇒ Auxiliary-input OWF); if the language is hard on average over a samplable distribution, one-way functions exist (Average-case-hard CZK ⇒ OWF) — OW93
  • Informally: any ZK proof that convinces a verifier of something hard must “hide” information in a computationally meaningful way, which requires a one-way function
• Few-round black-box zero knowledge exists only for $\mathbf{BPP}$. With negligible soundness error, every language with a three-message black-box zero-knowledge proof or argument, private-coin or public-coin, lies in $\mathbf{BPP}$ (Three-message black-box ZK ⊆ BPP), and so does every language with a constant-round public-coin one (Constant-round public-coin black-box ZK ⊆ BPP) — GK96a
  • Beyond three rounds the public-coin restriction is necessary: five-round private-coin black-box ZK proofs for NP exist assuming claw-free functions — GK96b. Four messages do not suffice for proofs: a language with a four-message black-box zero-knowledge proof with negligible soundness error lies in coMA (Four-message black-box ZK proofs ⊆ coMA) — Kat08
  • Two-message auxiliary-input zero knowledge with negligible soundness error exists only for languages in $\mathbf{BPP}$, whatever the simulator (Two-message auxiliary-input ZK ⊆ BPP) — GO94
  • For a language outside $\mathbf{BPP}$ and negligible soundness error, a constant-round black-box simulator must run in expected rather than strict polynomial time (Constant-round black-box ZK with strict polynomial-time simulation ⊆ BPP) — BL02
  • Under assumptions on program obfuscation, three-message private-coin zero-knowledge proofs for $\mathbf{NP}$ do not exist even with non-black-box simulation — FGJ18
• Parallel composition breaks ZK: repeating a ZK protocol in parallel to reduce soundness error may destroy the zero-knowledge property — GK96a. A public-coin protocol whose parallel repetitions are all black-box zero-knowledge exists only for languages in $\mathbf{BPP}$ (Public-coin black-box ZK under parallel repetition ⊆ BPP) — PTW09
• Concurrent black-box ZK needs almost logarithmically many rounds: a language outside $\mathbf{BPP}$ has no black-box concurrent zero-knowledge proof or argument with $o(\log n/\log \log n)$ rounds (Few-round black-box concurrent ZK ⊆ BPP) — CKPR01

Restricted zero-knowledge classes

A protocol is auxiliary-input zero-knowledge if for every efficient $V^{\ast }$ there is an efficient $\mathcal{S}$ such that for every $x\in L$, witness $w$ and auxiliary input $z$, $\mathcal{S}(x,z)$ is indistinguishable by non-uniform distinguishers from the view of $V^{\ast }(x,z)$ interacting with $P(x,w)$. It is black-box zero-knowledge if one expected-polynomial-time oracle machine $\mathcal{S}$ serves every verifier: for every efficient $V^{\ast }$ and every $x\in L$, ${\mathcal{S}}^{V^{\ast }}(x)$ is computationally indistinguishable from the view of $V^{\ast }$ — GO94. Each class below is a class of languages, admits interactive proofs or arguments (soundness against efficient provers only) unless it says proofs, and requires negligible soundness error. Each contains $\mathbf{BPP}$, whose languages have such protocols in which the verifier decides alone — standard.

Two-message auxiliary-input zero knowledge

The languages $L$ with a two-message interactive proof or argument (the verifier sends one message and the prover answers) with negligible soundness error that is auxiliary-input zero-knowledge — GO94.

Three-message black-box zero knowledge

The languages with a three-message interactive proof or argument, private-coin or public-coin, with negligible soundness error that is black-box zero-knowledge — GK96a.

Constant-round public-coin black-box zero knowledge

The languages with a public-coin interactive proof or argument with a constant number of messages and negligible soundness error that is black-box zero-knowledge — GK96a.

Public-coin black-box zero knowledge under parallel repetition

The languages with a public-coin interactive proof or argument with negligible soundness error whose $p(n)$-fold parallel repetition is black-box zero-knowledge for every polynomial $p$ — PTW09.

Four-message black-box zero-knowledge proofs

The languages with a four-message interactive proof, sound against unbounded provers, with negligible soundness error and possibly imperfect completeness, that is computational black-box zero-knowledge — Kat08.

Strict polynomial-time black-box simulation

The languages with a constant-round interactive proof or argument with negligible soundness error that is zero-knowledge with a black-box simulator running in strict, rather than expected, polynomial time — BL02. Negligible soundness error matters: one execution of the 3-coloring protocol of GMW91, whose soundness error is $1-1/|E|$, has a strict polynomial-time black-box simulator that guesses the challenged edge $n|E|$ times — standard.

Black-box concurrent zero knowledge in few rounds

The languages with a $k(n)$-round interactive proof or argument with negligible soundness error, $k(n)=o(\log n/\log \log n)$, that is black-box concurrent zero-knowledge. One expected-polynomial-time oracle machine simulates the joint view of every efficient verifier that runs polynomially many sessions with independent prover instances on common input $x$, interleaving and scheduling their messages adaptively — CKPR01.

Honest-verifier CZK

$\mathbf{HVCZK}$ is the class of languages with an interactive proof that is computational zero-knowledge against the honest verifier only: an efficient $\mathcal{S}$ outputs, for every $x\in L$, a distribution computationally indistinguishable from the view of the verifier that follows the protocol — Vad06.

Worst-case hardness

$\mathbf{CZK}⊈\mathbf{BPP}$ if some language $L\in \mathbf{CZK}$ is not in $\mathbf{BPP}$: for every PPT algorithm $\mathcal{A}$ there is an $x$ with $\mathrm{Pr}[\mathcal{A}(x)=L(x)]<2/3$ — standard.

Average-case hardness

$\mathbf{CZK}$ is hard on average if there are a language $L\in \mathbf{CZK}$ and a PPT sampler $D$ such that for all efficient $\mathcal{A}$,

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

the probability also over the coins of $\mathcal{A}$ — standard.

Participates in

Builds on Computational zero-knowledge

• Two-message auxiliary-input ZK ⊆ BPP (via Two-message auxiliary-input zero knowledge)
• Few-round black-box concurrent ZK ⊆ BPP (via Black-box concurrent zero knowledge in few rounds)
• Constant-round public-coin black-box ZK ⊆ BPP (via Constant-round public-coin black-box zero knowledge)
• Four-message black-box ZK proofs ⊆ coMA (via Four-message black-box zero-knowledge proofs)
• Public-coin black-box ZK under parallel repetition ⊆ BPP (via Public-coin black-box zero knowledge under parallel repetition)
• Constant-round black-box ZK with strict polynomial-time simulation ⊆ BPP (via Strict polynomial-time black-box simulation)
• Three-message black-box ZK ⊆ BPP (via Three-message black-box zero knowledge)
• Average-case-hard CZK ⇒ CZK ⊄ BPP (via Average-case hardness)
• Average-case-hard CZK ⇒ OWF (via Average-case hardness)
• CZK ⊆ IP
• HVCZK = CZK (via Honest-verifier CZK)
• CZK ⊄ BPP ⇒ Auxiliary-input OWF (via Worst-case hardness)

Produces Computational zero-knowledge

• Average-case-hard CZK ⇒ CZK ⊄ BPP (via Worst-case hardness)
• OWF + IP ⇒ CZK
• OWF ⇒ CZK
• HVCZK = CZK
• SZK ⊆ CZK