Class Description

SZK_h: SZK With Limited Help

The class of decision problems for which a "yes" answer can be verified by a statistical zero-knowledge proof protocol, and the prover and verifier both have access to a string computed by a trusted probabilistic polynomial-time third party with access to the input.

Defined in [BG03], where it was also shown that SZK_h = SZK.

Contains NISZK_h.

Linked From

NISZK_h: NISZK With Limited Help

The non-interactive analogue of SZK_h.

Defined in [BG03], where the following was also shown:

• NISZK_h contains NISZK and is contained in SZK.
• Graph Isomorphism is in NISZK_h.
• The following problem is complete for NISZK_h: Given two functions from {0,1}ⁿ to {0,1}ⁿ (specified by circuits), decide whether their ranges are almost equal or almost disjoint, given that one of these is the case.

The quantum lower bound for the set comparison problem in [Aar02] implies an oracle relative to which NISZK_h is not in BQP.

More about...