Given A, B, G, H .How would I prove that I know x such that $A=xG$ and $B=xH$
-
1$\begingroup$ See Chaum–Pedersen, or Fujisaki–Okamoto if the group has composite order? $\endgroup$ – Squeamish Ossifrage Jun 12 '19 at 16:02
There is a standard $\Sigma$-protocol for proving knowledge of a witness showing that $(G,H,A,B)$ is a DDH-tuple, assuming a group of prime order $p$:
- The prover picks a random exponent $r \in \mathbb{Z}_p$ and sends $(R,S) = (rG, rH)$.
- The verifier sends a random challenge $e$ from $\mathbb{Z}_p$.
- The prover computes and send $d = e\cdot x + r$.
- The verifier accepts the proof if and only if $eA+R = dG$ and $eB+S=dH$.
Since you seem to ask these questions for the purpose of learning, I'd suggest that you try to prove yourself the security of this protocol (that is, soundness, and honest-verifier zero-knowledge). You can take inspiration from the security analysis I gave for a similar protocol in this answer, that deals with the Schnorr protocol (about which you asked in another question).
-
$\begingroup$ Although it's taken me a long time to do (on and off), I have nearly completed this exercise without looking at the other links. Thank you for the inspiration $\endgroup$ – WeCanBeFriends Jul 17 '19 at 18:26