Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 Nov 28 '12 at 15:19
1  
@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 Nov 28 '12 at 16:02
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. –  Daniel Apon Nov 29 '12 at 13:32
1  
$\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}$ –  Ricky Demer Nov 30 '12 at 2:39
    
True, and thanks –  Daniel Apon Nov 30 '12 at 4:10
add comment

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
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? –  Johannes Nov 28 '12 at 16:05
1  
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$. $\:$ –  Ricky Demer Nov 28 '12 at 21:44
add comment

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

share|improve this answer
    
Thanks. This was what I guessed from the other posts :) –  Johannes Dec 4 '12 at 12:10
add comment

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.

share|improve this answer
    
Also, the simulator's $\sigma$ must be chosen from a different distribution than the real-world CRSs. –  Ricky Demer Mar 11 '13 at 3:05
    
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 Mar 14 '13 at 10:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.