6
$\begingroup$

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?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
15
  • $\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
    Commented Dec 20, 2015 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$ Commented Dec 20, 2015 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
    Commented Dec 20, 2015 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$ Commented Dec 20, 2015 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
    Commented Dec 20, 2015 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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