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$
$\endgroup$
5
-
$\begingroup$ What do the commitments look like? $\endgroup$– user991Dec 18, 2015 at 22:47
-
$\begingroup$ Pedersen Commitment: C(x) = g^xh^r $\endgroup$– HongyangDec 19, 2015 at 4:33
-
$\begingroup$ @Hongyang The value $c$ is secret? $\endgroup$– DrLecterDec 19, 2015 at 6:51
-
$\begingroup$ Challenge is something sent by Verifier to Prover while interactive proof, so $c$ probably is something else. $\endgroup$– Vadym FedyukovychDec 19, 2015 at 10:25
-
$\begingroup$ @DrLecter the challenge c is generated by the verifier and is public. $\endgroup$– HongyangDec 19, 2015 at 14:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
15
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.
answered Dec 19, 2015 at 10:38
-
$\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$– HongyangDec 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$ 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$– HongyangDec 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$ 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$– HongyangDec 20, 2015 at 18:51