1
$\begingroup$

For example, prover sends P = xG and verifier somehow sends back P = xH without learning x.

Is this possible?

Improve this question
$\endgroup$
4
$\begingroup$

For example, prover sends P = xG and verifier somehow sends back P = xH without learning x.

Yes; if the verify knows that $H = yG$, he just computes $P' = yP = xyG = xH$

Improve this answer
$\endgroup$
  • $\begingroup$ What if the verifier does not know the discrete log H wrt to G? $\endgroup$ – WeCanBeFriends Jun 4 '19 at 19:49
  • $\begingroup$ Then it's the Computational Diffie-Hellman (CDH) problem - difficult in the groups we use in crypto $\endgroup$ – poncho Jun 4 '19 at 20:07
  • 1
    $\begingroup$ Note that this is essentially the Diffie-Hellman key exchange protocol $\endgroup$ – Geoffroy Couteau Jun 5 '19 at 15:10
  • $\begingroup$ @GeoffroyCouteau: Hey! How am I supposed to maintain the illusion that I am wise and all-knowing, when people like you keep on pointing out that my answers are essentially trivial... :-) $\endgroup$ – poncho Jun 5 '19 at 19:08
  • $\begingroup$ Apologies! Next time I'll make sure to make a remark along the lines of "actually, this answer of poncho just solved in three lines a century-long open problem that Alan Turing himself had described as 'the greatest and probably hardest problem on computer science' in his seminal paper" :) $\endgroup$ – Geoffroy Couteau Jun 6 '19 at 18:03

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.