I'm supposed make some reductions but don't even know where to start. Any help would or explanation on how to do this would be much appreciated.


A reduction here would mean showing that if you had an efficient algorithm A to solve the discrete logarithm problem, then you could use that to construct an efficient algorithm B solving the computational Diffie-Hellman problem. (For starters, assume A always works and construct B that always works. For full credit, given A that works with some probability [over a uniform input], construct a B that works with the same probability [over uniform inputs].)

If you understand what the discrete logarithm and computational Diffie-Hellman problems are, a reduction should be immediate.

  • $\begingroup$ Do you have any examples about such reduction or some literature I can check to learn about this. thanks $\endgroup$ – CryptoNoob Mar 27 '20 at 14:11
  • $\begingroup$ @CryptoNoob Do you know how to program? Then think of it as a programming problem. You have a library (the algorithm A) that has some functionality (solving DL). You don't know how it works, you only know that it solves the problem correctly. Now come up with a program (the algorithm B) that solves the problem you are trying to solve (DDH or CDH). $\endgroup$ – Maeher Mar 27 '20 at 14:19

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.