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 ?
-
1$\begingroup$ medium.com/qed-it/the-incredible-machine-4d1270d7363a $\endgroup$– Vadym FedyukovychAug 9, 2018 at 8:33
3 Answers
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.
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
-
$\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$ Aug 9, 2018 at 16:11
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.
