2
$\begingroup$

Given an opening $(m, r)$ of a Pedersen commitment $c = g^m h^r$, where $g, h$ are the generators of a group $G$ with prime order $q$ (public), a PPT prover wants to prove to a verifier the opening of $c$ in zero-knowledge. Let us see the following procedure. Here we note that the DLP in $G$ is hard.

  1. Prover randomly pick $s, t < q$, computes $y = g^s h^t$.

  2. The verifier checks whether $y \in G$. If it is, the verifier sends a random challenge $e$ to the prover.

  3. The prover sends to the verifier $z_1 = s + em \bmod q$, $z_2 = t + er \bmod q$.

  4. The verifier accepts if $g^{z_1} h^{z_2} = y c^e$.

It seems that this argument works for our requirements. It is complete and special honest-verifier zero-knowledge.

But for the soundness, if a malicious prover provides $z_1' \ne z_1$, $z_2' \ne z_2$, such that $g^{z_1'}h^{z_2'} = yc^e$, it seems that such a prover can cheat in the procedure above. I know that a PPT prover cannot do this except for a negligible probability. But how can we formally prove this fact? Is it possible to provide a formal reduction that, if a malicious prover can cheat in this way, using this malicious prover we can provide two openings of a Pedersen commitment? If we can't, how can we show the soundness of this procedure? In a formal proof, do we need to always provide a reduction?

Improve this question
$\endgroup$
2
  • $\begingroup$ The problem with the statement "$z_1' \ne z_1$" is that implicitly assumes that, in step 1, the malicious prover actually did generate $y$ by selecting $s, t$; of course, a malicious prover would not be so constrained if he found an alternative to his advantage. It feels like you need a different strategy to prove that cheating implies you can solve the DLP (at least, $h$ to the base $g$) $\endgroup$
    – poncho
    Jun 8, 2020 at 19:26
  • $\begingroup$ @poncho Thank you very much for your comment. Could you please kindly provide a strategy for this purpose? $\endgroup$
    – Pure Air
    Jun 9, 2020 at 0:26

1 Answer 1

Reset to default
2
$\begingroup$

With this zero knowledge proof, the prover attempts to prove that he knows an opening of the commitment.

The obvious way to approach this is to show that, if the prover is able to complete the protocol for two different challenges, he is able to construct an opening of the commitment (and hence he actually knows what he is attempting to prove knowledge of).

How we show this is straight-forward:

  • Suppose the prover knows a value $y$ for which he can correctly answer two distinct challenge values $e, e'$. That is, if given the challenge $e$, he can answer with $z_1, z_2$ such that $g^{z_1}h^{z_2} = yc^e$, and if given the challenge $e'$, he can answer with $z'_1, z'_2$ such that $g^{z'_1}h^{z'_2} = yc^{e'}$

  • Then, given these values, the prover then knows:

    $$g^{(z_1-z'_1)(e - e')^{-1}}h^{(z_2-z'_2)(e - e')^{-1}} = c$$

That is, with valid answers to those two challenges, he can deduce an opening of the commitment.

Hence, someone who doesn't know a valid opening to the commitment can provide a valid answer at most one challenge to any $y$ value.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you very much for your answer. I am wondering whether this is computational soundness? Because I find that in some papers, the procedure is regarded as an argument of knowledge. But in this answer, it seems that it is not just computational soundness. $\endgroup$
    – Pure Air
    Jun 9, 2020 at 16:17
  • $\begingroup$ @PureAir: hmmm, reviewing this argument, I do see one subtle point; that the prover knows the two challenges that he would pass successfully. If he has a procedure for converting $e$ challenges into $z_1, z_2$ responses that works with probability $> 1/q$, but doesn't know which challenges would actually work, the argument doesn't apply. So, in that sense, it would appear to be somewhat computational... $\endgroup$
    – poncho
    Jun 9, 2020 at 17:11
  • $\begingroup$ Thank you very much. Does it mean that a prover could answer for some $e$, but he doesn't know which $e$ he can answer? I could not fully understand this. If this procedure is an argument of knowledge, how can we formally prove that it is computational soundness? Do we need to provide a reduction to break some computational assumptions? Looking forward to hearing from you. $\endgroup$
    – Pure Air
    Jun 10, 2020 at 0:58
  • $\begingroup$ @PureAir: I was speculating about a rather odd-ball case where my attempted proof did not apply; where the adversary could (with low but nonzero probability) generate a valid-looking proof while being ignorant of how to open the commitment. One odd thing about this odd-ball case is that the argument against it becomes stronger the more computational capability we assume the adversary has; if we assume that he can perform $2^x$ operations, then he can generate a false proof with probability no more than $2^{-x}$ or so; if the probability was higher, he could use this technique to open it. $\endgroup$
    – poncho
    Jun 10, 2020 at 2:55
  • $\begingroup$ @PureAir: also, note that I was not suggesting that this odd-ball case was possible; I was discussing a proof, and a proof needs to cover all cases, not merely the ones we think are plausible. And, I don't have a proof that this odd-ball case is impossible... $\endgroup$
    – poncho
    Jun 10, 2020 at 2:58

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.