Can we achieve statistical Completeness, Soundness and Zero Knowledge in an Interactive Proof?

Question

The question is mainly stated in the title, sorry for it being a bit small of a question. I was reading about ZK proofs and I was wondering what do we know about their limits only their properties. Do we have any impossibility theorems or any assumptions that we strongly believe that hold? Thanks in advance for your time.

Answer 1

The class of languages having statistical (resp. perfect) zero-knowledge proofs (where completeness is perfect and soundness statistical) is called $\mathsf{SZK}$ (resp. $\mathsf{PZK}$). Here is what we know about them:

• $\mathsf{PZK} \subseteq \mathsf{SZK} \subseteq \mathsf{AM}\cap\mathsf{coAM}$

$\mathsf{AM}$ is the Arthur-Merlin class, it is in a sense "just above" the class $\mathsf{NP}$. The result above comes from the inclusion $\mathsf{SZK} \subseteq \mathsf{AM}$ and the proof that $\mathsf{SZK}$ is closed by complement. An important consequence of this result is that if $\mathsf{NP} \subseteq \mathsf{SZK}$ (i.e. $\mathsf{SZK}$ contains all of $\mathsf{NP}$), then $\mathsf{NP}$ is closed by complement. This is believed to be highly unlikely, as it would cause the polynomial hierarchy to collapse (i.e. all the infinitely-many "higher" complexity classes of the $\mathsf{NP}$ hierarchy would suddendly "collapse" to $\mathsf{NP}$). You can find a few pointers to the references in section 3.2.2 of my thesis.

• $\mathsf{SZK}$ contains $\mathsf{BPP}$ (the class of languages which we can solve efficiently - in polynomial time - with a probabilistic algorithm), and it is likely that this containment is strict. Indeed, $\mathsf{SZK}$ contains multiple languages which are not known, or even not believed, to be in $\mathsf{BPP}$, such as graph non-isomorphism, but also a variety of hard lattice problems, as well as most discrete-log related problems (the classical $\Sigma$-protocol for proving that a DDH tuple is well-formed is in $\mathsf{SZK}$, as are most $\Sigma$-protocols), protocols for quadratic residuosity, etc.
• Actually, it is not even clear whether $\mathsf{SZK}$ is contained in $\mathsf{NP}$, since it contains graph non-isomorphism, which is not known to be in $\mathsf{NP}$.

To sum it up, the class $\mathsf{SZK}$ contains many interesting languages, including many languages conjectured to be hard, and even some not known to be in $\mathsf{NP}$. However, it is not believed to contain an $\mathsf{NP}$-complete language (equivalently, to contain all of $\mathsf{NP}$), as it would cause the polynomial hierarchy to collapse.