<p>I think you are confusing zero knowledge with soundness.</p>

<p>Fix some language $L$.</p>

<p>[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.</p>

<p>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$. </p>

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

CC BY-SA 3.0
2012-12-02T19:35:35.603Z
2012-12-02T19:35:35.603Z
user6584
<p>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$.</p>

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

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2013-03-14T10:15:26.120Z
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.
cryptocat
CC BY-SA 3.0
2013-03-10T18:04:10.383Z
2013-03-10T18:04:10.383Z
cryptocat
<p>In NIZK proofs, the prover can generate its proof for statement $y$ and witness $w$ using</p>

<p>$$\pi \gets \mathrm{Prove}(\sigma,y,w)\text{,}$$</p>

<p>where $\sigma$ is the common reference string. Source: <a href="http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof" rel="nofollow">Wikipedia</a>.</p>

<p>However, the zero knowledge property tells us that everyone could have generated a pair $(\sigma, \pi)$ itself. Source: <a href="http://en.wikipedia.org/wiki/Zero-knowledge_proof" rel="nofollow">Wikipedia</a>.</p>

<p>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?</p>

CC BY-SA 3.0
2012-11-28T15:19:08.540Z
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?
Daniel Apon
CC BY-SA 3.0
2012-11-28T16:02:43.703Z
@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?
Johannes
CC BY-SA 3.0
2012-11-29T13:32:25.023Z
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.
Daniel Apon
<cr.crypto-security><interactive-proofs><zero-knowledge>
NIZK proofs: Why is the prove function necessary?
Johannes
# NIZK proofs: Why is the prove function necessary?

(Asked by: username_0 on 2012-11-28)

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](http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof).

However, the zero knowledge property tells us that everyone could have generated a pair $(\sigma, \pi)$ itself. Source: [Wikipedia](http://en.wikipedia.org/wiki/Zero-knowledge_proof).

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?

**Tags:** cr.crypto-security, interactive-proofs, zero-knowledge

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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?  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2012-12-02. Score: 2

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$.


---

### Answer by username_3 on 2013-03-10. Score: 1

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.

> **Comments:**
> **username_3**: 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.  

---

