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.)
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]. (Previously, these properties were only established in the presence of one-way functions [GMW91].)
Assuming the existence of one-way functions, CZK contains NP [GMW91], and actually equals IP=PSPACE [BGG+90]. However, none of these implications of one-way functions relativize (Impagliazzo, unpublished).
On the other hand, if one-way functions do not exist then CZK = AVBPP [OW93].
The class of decision problems solvable by a Turing machine in polynomial space.
Equals NPSPACE [Sav70], AP [CKS81], and CZK assuming the existence of one-way functions [BGG+90].
Equals IP [Sha90], but PSPACE strictly contains IP with probability 1 [CCG+94].
Contains P#P (P with a #P oracle).
A canonical PSPACE-complete problem is QBF.
Relative to a random oracle, PSPACE strictly contains PH with probability 1 [Cai86].
PSPACE has a complete problem that is both downward self-reducible and random self-reducible [TV02]. It is the largest class with such a complete problem.
Contained in EXP. There exists an oracle relative to which this containment is proper [Dek76].
In descriptive complexity, PSPACE can be defined with 4 differents kind of formulae, FO() which is also FO(PFP) and SO() which is also SO(TC).
Same as SZK, but now the two distributions must be identical, not merely statistically close. (The "two distributions" are (1) the distribution over the verifier's view of his 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.)
Contained in SZK and HVPZK.There are oracles separating PZK from SZK, coPZK, NIPZK, and coSBP. [BCHTV17], [DGPV20].
See also: CZK.
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).
What does that mean? For each choice of random coins, the verifier has a "view" of his entire interaction with prover, consisting of his random coins as well as all messages sent back and forth. Then the distribution over views resulting from interaction with the prover has to be statistically close to a distribution that the verifier could generate himself (in polynomial-time), without interacting with anyone. (Here "statistically close" means that, say, the trace distance is at most 1/10.)
The most famous example of such a protocol is for graph nonisomorphism. Given two graphs G and H, the verifier picks at random one of the graphs (each with probability 1/2), permutes its vertices randomly, sends the resulting graph to the prover, and asks, "Which graph did I start with, G or H?" If G and H are non-isomorphic, the prover can always answer correctly (since he can use exponential time), but if they're isomorphic, he can answer correctly with probability at most 1/2. Thus, if the prover always gives the correct answer, then the verifier becomes convinced the graphs are not isomorphic. On the other hand, the verifier already knew which graph (G or H) he started with, so he could simulate his entire view of the interaction himself, without the prover's help.
If that sounds like a complicated definition, well, it is. But it turns out that SZK has extremely nice properties. [Oka96] showed that:
Subsequently, [SV97] showed that SZK has a natural complete promise problem, called Statistical Difference (SD). Given two polynomial-size circuits, C0 and C1, let D0 and D1 be the distributions over their respective outputs when they're given as input a uniformly random n-bit string. We're promised that D0 and D1 have trace distance either at most 1/3 or at least 2/3; the problem is to decide which is the case.
Note: The constants 1/3 and 2/3 can be amplified to 2-poly(n) and 1-2-poly(n) respectively. But it is crucial that (2/3)2 > 1/3.
Another complete promise problem for SZK is Entropy Difference (ED) [GV99]. Here we're promised that either H(D0)>H(D1)+1 or H(D1)>H(D0)+1, where the distributions D0 and D1 are as above, and H denotes Shannon entropy. The problem is to determine which is the case.
If any hard-on-average language is in SZK, then one-way functions exist [Ost91].
See general zero-knowledge (ZK).
Contains PZK and NISZK, and is contained in AM ∩ coAM, as well as CZK and QSZK.
There exists an oracle relative to which SZK is not in BQP [Aar02].
Often used as a shorthand for (computational zero-knowledge) CZK, but may also be used as a general paradigm encomposing various classes ranging from perfect and statistical zero-knowledge (SZK) to computational ones (CZK), and also various forms of non-interactive zero-knowledge proof systems.
Zero-knowledge proofs were introduced in [GMR89], and further studied in [GMW91], which demonstrated the wide applicability of the concept.
