I have two secret values $L_1$, $L_2$, and two Pedersen commitments $C_1 = C(L_1)$, $C_2=C(L_2)$. The commitments $C_1$, $C_2$ are public. Given a challenge $c$, I want to output $d = c*L_1+L_2$ and prove in zero-knowledge that $d$ is formed correctly. What should the zero-knowledge proof look like?

  • $\begingroup$ What do the commitments look like? ​ ​ $\endgroup$ – user991 Dec 18 '15 at 22:47
  • $\begingroup$ Pedersen Commitment: C(x) = g^xh^r $\endgroup$ – Hongyang Dec 19 '15 at 4:33
  • $\begingroup$ @Hongyang The value $c$ is secret? $\endgroup$ – DrLecter Dec 19 '15 at 6:51
  • $\begingroup$ Challenge is something sent by Verifier to Prover while interactive proof, so $c$ probably is something else. $\endgroup$ – Vadym Fedyukovych Dec 19 '15 at 10:25
  • $\begingroup$ @DrLecter the challenge c is generated by the verifier and is public. $\endgroup$ – Hongyang Dec 19 '15 at 14:20

Consider a multiplicative group of an order $q$ generated by some $g$. For simplicity, let commitment be $C_1 = g^{L_1}$. Consider a proof of knowledge of $L_1$ committed to at $C_1$. At the first step of an interactive proof, choose some $L_2$ at random and send $C_2 = g^{L_2}$ to the verifying party. Second step, receive a challenge $c$. Third step, send a response $d = c L_1 + L_2 \pmod{q}$. Now verify this response with $g^d=$ something computable by the verifying party. That is, an expression of something that was sent to verifying party before or while running the protocol.

| improve this answer | |
  • $\begingroup$ Thanks for the explanation. One question: does this simultaneously prove that the prover knows the value $L_1$ and $L_2$ committed in $C_1$ and $C_2$ respectively? $\endgroup$ – Hongyang Dec 20 '15 at 16:46
  • $\begingroup$ This explanation is not complete yet. Did you get verification equation? Did you read Schnorr protocol? To be a proof of knowledge, such a protocol must admit an extractor algorithm that would output the value committed. $\endgroup$ – Vadym Fedyukovych Dec 20 '15 at 18:31
  • $\begingroup$ The verifier is given $d$, $C_1 = g^{L_1}$ and $C_2 = g^{L_2}$, and verifies that $g^d = (C_1)^cC_2$, right? $\endgroup$ – Hongyang Dec 20 '15 at 18:35
  • $\begingroup$ Right. Please note it is essential that Prover is given challenge $c$ only after he sends his first protocol message, commitment $C_2$. Next, to be zero knowledge, a proof must admit simulator algorithm that would output simulated transcript. $\endgroup$ – Vadym Fedyukovych Dec 20 '15 at 18:44
  • $\begingroup$ I'm not sure I get the point about the simulated transcript. Why is the current proof incomplete? Could you elaborate a little bit? I really appreciate your help. $\endgroup$ – Hongyang Dec 20 '15 at 18:51

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.