2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ I hope the requirement to have P as a subset is not too restrictive, if it is, please tell me. $\endgroup$
    – SEJPM
    Jan 23, 2021 at 14:51
  • $\begingroup$ 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). $\endgroup$
    – ckamath
    Jan 25, 2021 at 1:08
  • $\begingroup$ @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. $\endgroup$
    – SEJPM
    Jan 25, 2021 at 10:42
  • 1
    $\begingroup$ 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). $\endgroup$
    – Geoffroy Couteau
    Jan 25, 2021 at 15:50

1 Answer 1

Reset to default
2
$\begingroup$

The sumcheck protocol can be made non-interactive, both in the random oracle model and under strong cryptographic assumptions. Good starting points to read about that are this paper and this paper. The high level intuition that even if Fiat-Shamir fails in general for interactive protocols with many rounds, it holds whenever the protocol satisfies some stronger notion of round by round soundness which the sumcheck protocol does satisfy.

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.

Edit: An important point, though, is that this result in the ROM will not be easy to extend to the standard model, at least not with standard cryptographic assumptions. This is because to get a constant-round argument for a language outside of NP, we would need a cryptographic assumption (for the soundness) which withstands even attacks from prover which are given the power of this larger complexity class, and this is typically not something given by standard cryptographic assumptions.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.