Why is a common reference string needed in zero knowledge proofs?

Question

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

Answer 1

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)

• PZK: Quadratic residuosity, graph isomorphism
• SZK: Quadratic non-residuosity, graph non-isomorphism, lattice problems like CVP
• CZK: Graph coloring (and in fact as Geoffroy points out any language in IP)

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).

Answer 2

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).