Computational zero-knowledge (CZK)

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.

Notable problems

• 3-coloring — assuming OWFs exist

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 and may as well show their coins, and CZK is closed under unions. — Vad06
• Assuming OWFs exist, CZK contains NP — GMW91
  • And, in fact CZK actually equals IP=PSPACE — BGG+90
• Contains SZK