3
$\begingroup$

Given a Pedersen Commitment:

$P = aG + vH$

Where $G$ and $H$ are points in some group. $a$ is a blinding value/mask and $v$ is the value I wish to commit to.

Is there a way to prove I know $v$ without revealing it?

$\endgroup$
2
$\begingroup$

This extension of the Schnorr protocol would appear to work:

$P := aG + vH$

$\operatorname{GenProof}(a, v)$:

  1. $x, y \leftarrow Z_q$
  2. $P' := xG + yH$
  3. $t := RandomOracle(P')$ (alternatively, the verifier picks $t$ after learning $P'$)
  4. $x' := x + ta, y' := y + tv$
  5. return $(P', x', y')$

$\operatorname{Verify}(P, P', x', y')$:

  1. $t := RandomOracle(P')$
  2. accept if $x'G + y'H = P' + tP$
$\endgroup$
  • $\begingroup$ Is this more of a proof stating that I know a tuple (a,v) that make P? I think my original question may be impossible, because pedersen commitments are not perfectly hiding. I like this proof though extending it from n=1 excluding the blinder, to n=m scalar, I can prove that I know all m values in a given pedersen commitment plus the blinder. Very cool! If I'm understanding correctly that is :D $\endgroup$ – WeCanBeFriends Feb 12 at 22:42
  • $\begingroup$ @WeCanBeFriends: to prove you know $a$, you also need to prove that you know $v$. After all, for any $a'$, there exists a $v'$ with $P = a'G + v'H$. And, Pedersen commitments are perfectly hiding (in fact, because of the existance of $v'$) $\endgroup$ – poncho Feb 12 at 22:47
0
$\begingroup$

There are multiple zero knowledge proofs to solve this problem (for example Bulletproofs which are quite efficient but very complicated so I will describe a simpler scheme below. I actually don't know anymore where I saw this scheme so I can't provide any references or security proofs.

$\operatorname{GenProof}(a, v)$:

  1. $r \leftarrow Z_q$
  2. $P' := rG + vH$ so that $A := P - P' = (aG + vH) - (rG + vH) = (a-r)G$
  3. Use a normal signature scheme like EcDSA to sign an empty message for $A$.
  4. return $(P', \text{signature})$

$\operatorname{Verify}(P, P', \text{signature})$:

  1. $A = P - P'$
  2. return $\operatorname{signature\_verify}(\text{signature}, A, \text{empty_message})$

EDIT: I just came up with a very trivial attack on this scheme, DO NOT USE IT.

$\operatorname{Attack}(P)$:

  1. $a \leftarrow Z_q$, $A := aG$
  2. $P' = P + A$
  3. Proceed as usual
$\endgroup$
  • $\begingroup$ the message is signed with a-r ? How does this prove that I know the v s.t. P = aG + vH? $\endgroup$ – WeCanBeFriends Jan 13 at 20:04
  • $\begingroup$ Yeah, I just had the same idea, it does not proof anything at all. Will edit my post and try to find the source of the proof. $\endgroup$ – VincBreaker Jan 13 at 20:06
  • $\begingroup$ @VincBreaker, we are waiting for your feedback on looking for the source that inspired your sketch above. Anyway, you already gave us a lot of tips here... $\endgroup$ – McFly Feb 15 at 16:48
  • $\begingroup$ @McFly Sadly, I wasn't able to find it anymore, so I also really would like to know where it came from. I remember the paper being about another zero-knowledge proof of some kind which required proofing the knowledge $(a, v)$ at some point but I can't give anymore information. If someone comes across this paper, feel free to let us know :) EDIT: Actually there is some more information: I read it arround a year ago so it has to be at least a year old, but I read a lot about ZKP's a year ago :/ $\endgroup$ – VincBreaker Feb 18 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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