4
$\begingroup$

In NIZK proofs, the prover can generate its proof for statement $y$ and witness $w$ using

$$\pi \gets \mathrm{Prove}(\sigma,y,w)\text{,}$$

where $\sigma$ is the common reference string. Source: Wikipedia.

However, the zero knowledge property tells us that everyone could have generated a pair $(\sigma, \pi)$ itself. Source: Wikipedia.

So what is prove needed for? I guess it is needed, because the verifier forces the prover to use a given common reference string $\sigma$? This is probably the reason why the verifier can not convince any other verifier?

Improve this question
$\endgroup$
4
  • $\begingroup$ I believe you're only thinking about the security proof (whose entire point is to remove the dependence on the witness $w$ to achieve ZK). How do you suggest using the NIZK in a construction (e.g. ssNIZK for Naor-Yung CCA) without a protocol for a party to generate proofs? $\endgroup$
    – Daniel Apon
    Nov 28, 2012 at 15:19
  • 1
    $\begingroup$ @DanielApon My idea was to just let the prover generate the proof $\pi$ without even needing the Witness $w$ (though the prover knows $w$). The ZK property tells us that $\pi$ can be constructed without knowing $w$. However, I think this does not work, because the proof $\pi$ shall be computed for a given CRS. Correct? $\endgroup$
    – Johannes
    Nov 28, 2012 at 16:02
  • 1
    $\begingroup$ Yes, precisely. The simulator is not expected to be able to give proofs relative to a uniformly distributed $\sigma$; all that is required is that $\sigma$ (output by the simulator) is computationally indist. from a uniformly distributed CRS. As such, ZK is achieved by having Sim output a pseudorandom $\sigma$, which is a different situation than the one where a prover (without access to Prove and $w$) attempts to generate $\pi$ from a uniformly distributed $\sigma$, as you've suggested. $\endgroup$
    – Daniel Apon
    Nov 29, 2012 at 13:32
  • 1
    $\begingroup$ $\sigma$ (output by the simulator) is only required to be computationally indistinguishable $\hspace{.7 in}$ from an honestly generated CRS (not necessarily a uniformly distributed CRS). $\hspace{.8 in}$ $\endgroup$
    – user6973
    Nov 30, 2012 at 2:39

3 Answers 3

Reset to default
4
$\begingroup$

Prove$\:\:$is needed to convince the verifer(s) that $y$ is true.
Sort of; the verifier(s) will have almost as much control as the prover over the choice of $\sigma$.
The verifier(s) can convince (every) other verifier by forwarding $\pi$ to the other verifier(s).
Unlike ZK protocols in the standard model, which have
deniability, NIZK proofs instead have transferability.

Related to NIZK but not otherwise related to your question:
multi-string NIZK uses a weaker setup assumption.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So the fact that the CRS $\sigma$ is given before the proof shall be generated is the reason why the prover needs the witness $w$ to generate the proof? $\endgroup$
    – Johannes
    Nov 28, 2012 at 16:05
  • 1
    $\begingroup$ No, the fact that the CRS $\sigma$ was generated honestly is the reason why it's not necessarily $\hspace{.66 in}$ easy to generate the proof without the witness $w$. $\:$ $\endgroup$
    – user6973
    Nov 28, 2012 at 21:44
2
$\begingroup$

I think you are confusing zero knowledge with soundness.

Fix some language $L$.

[Adaptive] soundness for NIZK says, roughly, that when $\sigma$ is chosen at random a prover cannot find a $y \not \in L$ and a proof $\pi$ for which a verifier will accept.

Zero knowledge says that, for any $y \in L$, a simulator can output $(\sigma, \pi)$ that is indistinguishable from $\sigma$ being chosen at random and then an honest prover generating a proof $\pi$ for $y$.

It makes a huge difference whether $\sigma$ is chosen first, or whether the simulator gets to choose $\sigma$.

Improve this answer
$\endgroup$
0
1
$\begingroup$

The prover and the simulator must both be able to generate the proof, but given different inputs. The Prove functionality gets as input the CRS $\sigma$, the statement $y$ and the witness $w$, and outputs $\pi$.

The soundness requirement postulates that nobody should be able to create $\pi$ for $y \not\in L$, given $\sigma$ as an input.

However, zero-knowledge requirement says that simulator must be able to create $\pi$ even without knowing $w$. To get soundness and ZK at the same time, the simulator must get an extra input, which is some trapdoor $\tau$ generated while $\sigma$ was chosen. For example, the trapdoor could be the secret key corresponding to the public key that is contained in $\sigma$. Thus, in the simulation functionality, the simulator gets inputs $(\sigma, \tau, y)$ and outputs $\pi$.

In the real world, the prover does not know the trapdoor and thus must use the Prove functionality. Inside the proof however, while proving that the proof does not leak prover's secret input, the simulator creates $\pi$ based on the simulation functionality. If he can do it, then the ZK property is obvious. It is also obvious that this does not contradict the soundness property.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Also, the simulator's $\sigma$ must be chosen from a different distribution than the real-world CRSs. $\endgroup$
    – user6973
    Mar 11, 2013 at 3:05
  • $\begingroup$ Not definitely from a different distribution. There are NIZK proofs systems where simulator's $\sigma$ is exactly the same as in the case of the real proof, the only difference is that the simulator also knows the corresponding trapdoor. Also, for the security of the overall proof system, it is obviously required that both $\sigma$-s are (statistically/computationally) indistinguishable. $\endgroup$
    – cryptocat
    Mar 14, 2013 at 10:15

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.