Converting common reference string to common random string

Question

I listened to a talk on NIZK a while ago and vaguely remembered the speaker mentioned something like - A scheme that is statistically sound and computationally ZK in common reference string model could become computationally sound and statistically ZK in common random string model.

I couldn’t remember the exact talk and speaker, but I’m wondering whether this kind of duality is common in CRS constructions, and if so, how do we convert a scheme in common reference string model into one in common random string model?

Thanks!

Answer 1

There is no generic conversion, but it is a standard property of dual-mode NIZKs. Here, the CRS comes in two indistinguishable modes, where one is structured, but the other is actually a truly random string. Typically, in group-based construction, the random CRS will be a tuple of random group elements, while the structured CRS will be a DDH tuple - both will then be indistinguishable under the DDH assumption.

At a very high level, the reference string will be used as a parameter of some commitment scheme in which you put the witness in the NIZK. Then, using some appropriate construction of commitments, the commitment can be perfectly hiding as long as the CRS is random, but becomes perfectly binding as soon as the CRS is structured. Think for example about Groth-Sahai-style dual-mode commitments, which have a similar property.

Some recent examples of NIZKs with this property include this work.