Class Description

NIPZK: Non-Interactive PZK

Defined in [M08] based on [DDPY98],[BFM88].

Contained in PZK and coSBP.There are oracles separating NIPZK from PZK, coNIPZK, and SBP [BCHTV17], [DGPV20].

[M08] showed a complete promise-problem for NIPZK, called Uniform (UN). Instances in UN are circuits with n+1 output bits. The first n bits represent the uniform distribution, and the last bit is 1 with probability at least 2/3. For instances not in UN, when the last bit is 1, at most 1/3 of the strings of length n can appear as the output of the circuit. The problem is to decide which is the case. [DGPV20] showed Uniform is in coSBP.

Linked From

PZK: Perfect Zero Knowledge

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.

More about...