Class Description

HVSZK: Honest-Verifier SZK

The class of decision problems that have SZK protocols assuming an honest verifier (i.e. one who doesn't try to learn more about the problem by deviating from the protocol).

Equals SZK [Oka96].

Linked From

QSZK: Quantum Statistical Zero-Knowledge

A quantum analog of SZK (or more precisely HVSZK).

Arthur is a BQP (i.e. quantum) verifier who can exchange quantum messages with Merlin. So Arthur and Merlin's states may become entangled during the course of the protocol.

Arthur's "view" of his interaction with Merlin is taken to be the sequence of mixed states he has, over all steps of the protocol. The zero-knowledge requirement is that each of these states must have trace distance at most (say) 1/10 from a state that Arthur could prepare himself (in BQP), without help from Merlin. Arthur is assumed to be an honest verifier.

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

• QSZK is contained in PSPACE.
• QSZK is closed under complement.
• Any protocol can be parallelized to consist of two messages, so that QSZK is in QIP[2].
• One can assume without loss of generality that protocols are public-coin, as for SZK.
• QSZK has a natural complete promise problem, called Quantum State Distinguishability (QSD). We are given quantum circuits Q₀ and Q₁. Let ρ₀ and ρ₁ be the mixed states they produce respectively, when run on the all-0 state (and when non-output qubits are traced out). We are promised that the trace distance between ρ₀ and ρ₁ is either at most α or at least β, where α and β are constants in [0,1] satisfying α < β². The problem is to decide which of these is the case.

Subsequently, [Wat09b] showed that honest-verifier and general-verifier quantum statistical zero-knowledge are equivalent.

There exists an oracle relative to which QSZK does not contain UP ∩ coUP, and a random oracle relative to which QSZK does not contain UP [MW18].

More about...