# What language classes beyond NP allow constant-round zero-knowledge proofs?

While discussing proving a language in $$\Sigma_2$$ from a client to a server with a friend we realized that while we know that such a language is provable in zero-knowledge, we didn't know whether it was provable in non-interactive zero-knowledge. This then led us to find this answer which states it is sufficient for a zero-knowledge proof to be constant-round to be transformable into a non-interactive one via Fiat-Shamir.

This then led me to confirm that in fact NP allows constant-round zero-knowledge proofs (PDF), which of course lead to the question in the title.

So:
Which language classes that include P allow constant-round zero-knowledge proofs - other than P and NP - and for which do we know that every zero-knowledge proof needs to have non-constant number of rounds?

• I hope the requirement to have P as a subset is not too restrictive, if it is, please tell me. Jan 23, 2021 at 14:51
• As far as I know, even the best interactive proof for $\mathbf{coNP}$, which is contained in $\Sigma_2$, requires "linear" number of rounds of interaction (via the sumcheck protocol). I believe there are negative results out there which say that this is inherent (e.g, here). Jan 25, 2021 at 1:08
• @Occams_Trimmer yeah, already that paper's abstract gives a strong suggestion that you can't have constant-round proofs (and thus NIZKs) for coNP. And I think most strengthenings of NP also include coNP (?). I think (with a short sketch of the proof?) that would be acceptable as an answer to me. Jan 25, 2021 at 10:42
• Note that the limitations of this paper are only for proofs, and not for arguments - i.e., they only rule out interactive proofs where the soundness is unconditional. No such bound exist (nor is believed to exist) if one extends the question to interactive argument, where soundness is computational and holds only against bounded adversaries (which is what Fiat-Shamir can give you). Jan 25, 2021 at 15:50

This gives you a non-interactive argument for $$\#\mathsf{P}$$ in the ROM. I believe that it should be relatively easy to make it zero-knowledge. It might extend to all of PSPACE, though one would have to check the details - I do not think it has been written formally anywhere.