1
$\begingroup$

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

|improve this question
$\endgroup$
  • 1
    $\begingroup$ See Chaum–Pedersen, or Fujisaki–Okamoto if the group has composite order? $\endgroup$ – Squeamish Ossifrage Jun 12 '19 at 16:02
3
$\begingroup$

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

|improve this answer
$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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