Zero-Knowledge Proof of a polynomial

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?

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