4
$\begingroup$

Can we have a non-trivial language without a CRS? Why?

$\endgroup$
  • 1
    $\begingroup$ Does the Swiss voting back door answer this? $\endgroup$ – Squeamish Ossifrage Jun 6 at 13:53
  • $\begingroup$ @SqueamishOssifrage Yes, also a good elaborate example $\endgroup$ – WeCanBeFriends Jun 6 at 14:08
  • 1
    $\begingroup$ Do you mean NIZKs? $\endgroup$ – Occams_Trimmer Jun 6 at 14:36
  • $\begingroup$ @Occams_Trimmer I was not being specific, however if you have any insight on NIZK specifics then it would also be helpful $\endgroup$ – WeCanBeFriends Jun 6 at 14:45
  • 1
    $\begingroup$ If interaction is allowed then there are quite a lot of examples: take any language in the classes PZK/SZK/CZK. However, only languages in BPP have NIZK proofs without CRS. $\endgroup$ – Occams_Trimmer Jun 6 at 14:51
3
$\begingroup$

Any language in the classes PZK (perfect zero-knowledge), SZK (statistical zero-knowledge) or CZK (computational zero-knowledge) have interactive protocols that are zero knowledge and don't require a CRS. Some of the interesting non-trivial languages in these classes are listed below. (I'd also recommend this beautiful survey by Vadhan)

However, Oren [O] showed that only languages in BPP have NIZK proofs without CRS. You can find a proof sketch here (Lemma 1).

[O]: Oren. On the cunning power of cheating verifiers: Some observations about zero knowledge proofs (behind a paywall unfortunately).

$\endgroup$
  • $\begingroup$ Is Honest-Verifier-Zero-Knowledge in CZK? $\endgroup$ – WeCanBeFriends Jun 6 at 15:15
  • 1
    $\begingroup$ Since (assuming OWF) CZK = PSPACE = IP, every language that has an interactive proof, zero-knowledge or not, is in CZK. $\endgroup$ – Geoffroy Couteau Jun 6 at 15:25
5
$\begingroup$

To complement a bit the answer of Occams_Trimmer: a CRS matters strongly for obtaining zero-knowledge proofs with a small number of rounds and for a large class of languages.

Without a CRS and without restriction on the number of rounds, as Occams_Trigger mentioned, we get the class CZK. This is a very large class: under the minimal assumption that one-way functions exist, it is actually equal to the huge class PSPACE. If we limit our attentions to zero-knowledge proofs with an efficient (polynomial time) prover, then it becomes equivalent to NP (i.e., essentially the class of all languages we care about).

However, without a CRS, it is much harder to get a small number of rounds: assuming only one-way functions, we need a superconstant number of rounds to get zero-knowledge proofs for NP. Assuming further the existence of collision-resistant hash functions, we can build five rounds zero-knowledge proofs for NP. This is essentially the best we can hope for: under black-box simulation, a 4-round zero-knowledge proof for NP would collapse the polynomial hierarchy (but there exists some candidate constructions based on exotic assumptions, such as knowledge-of-exponent assumptions or keyless multi-collision resistant hash functions, with non-black-box simulation). Even with non-black-box simulation, a 3-round ZK proof for NP would break indistinguishability obfuscation. Furthermore, 2-round ZK proofs can simply not exist for languages outside BPP.

In contrast, with a CRS, every language in NP has a non-interactive (1-round) zero-knowledge proof, under standard assumptions (e.g. factorization).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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