2
$\begingroup$

I would like to have some explanations about Non Interactive Zero Knowledge Proof. I saw with an example how to use the Fiat-Shamir transformation on Schnorr identification scheme to get a NIZK and I understood how it works in the random oracle model.
What I don't understand is how does a NIKZ work in the common reference string model (CRS). If I understand it right, the principe is that the CRS is generated in a trusted way and is used by the prover and the verifier to establish the truth of a statement.
Without worrying about the generation of this CRS, I would like to know how an algorithm works with a concrete example. I found lots of examples in the random oracle model but I didn't find any with a CRS. Can someone explain to me or give me some links that illustrate this concept in a more practical way, for example with a demo implemented in some language or from a library ?

$\endgroup$
1
$\begingroup$

Recently it is shown that prover does not need to trust CRS generator/s to get ZK property, you may read more details on https://eprint.iacr.org/2017/599 and https://eprint.iacr.org/2017/587.

Regard to an instance of NIZK proofs, I would recommend Pinocchio, a succinct NIZK system in the CRS model, which has a nice example and implementation. More on, https://www.microsoft.com/en-us/research/publication/pinocchio-nearly-practical-verifiable-computation/

By the way, Pinocchio has focused on verifiable computations and particularly in this NIZK system, CRS elements are generated by verifier which is not the case in general.

$\endgroup$
1
$\begingroup$

A NIZK in the CRS model consists of algorithms $(\operatorname{Setup}, \operatorname{Prove}, \operatorname{Verify})$ where $$\operatorname{Setup}(1^\lambda)\rightarrow (\sigma, \tau)$$ generates a public CRS $\sigma$ and a verification state $\tau$. The proving algorithm $$\operatorname{Prove}(\sigma, x, w)\rightarrow \pi$$ uses the CRS, a statement and a witness to produce a proof $\pi$, which the verifier can check using the verification state $$\operatorname{Verify}(\tau, x, \pi) \rightarrow 0/1.$$

Such NIZK systems exist for virtually any statement you could be interested in, namely for any $\textbf{NP}$ relation. You can find an implementation of a NIZK for Boolean circuit satisfiability here: https://github.com/scipr-lab/libsnark

$\endgroup$
  • $\begingroup$ What I wanted to know was more what's in the Prove and Verify algorithms. But I will look at your link. Thank you $\endgroup$ – user1990088 Aug 9 '18 at 16:11
0
$\begingroup$

Check out the notes for lectures 11-13 here: http://www.cs.umd.edu/~jkatz/gradcrypto2/scribes.html The notes explain how NIZK proofs can be constructed in the CRS model based on trapdoor permutations.

$\endgroup$
  • $\begingroup$ Could you please edit your answer to provide an overview / a summary of how the linked resource answers the question in case the resource goes down? $\endgroup$ – SEJPM Aug 11 '18 at 9:15

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.