# Given A, B, G, H prove the I know x s.t. $A=xG$ and $B=xH$

Given A, B, G, H .How would I prove that I know x such that $$A=xG$$ and $$B=xH$$

• See Chaum–Pedersen, or Fujisaki–Okamoto if the group has composite order? – Squeamish Ossifrage Jun 12 at 16:02

## 1 Answer

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).

• 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 – WeCanBeFriends Jul 17 at 18:26