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.
1 Answer
$\begingroup$
$\endgroup$
2
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$ Mar 27, 2020 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$– MaeherMar 27, 2020 at 14:19