2
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I was searching for a paper/article that describes this for a while. Thanks for the help! If the two modes are indistinguishable, we don't know how the CRS is created and therefore don't know whether the commitment is statistically or computationally binding/hiding - does this improve the security property of the commitment scheme over a normal single-mode commitment scheme? $\endgroup$
    – Steven Yue
    Oct 17, 2020 at 5:55

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.