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$CryptoNoob– CryptoNoob2020-03-27 14:11:58 +00:00Commented 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$Maeher– Maeher2020-03-27 14:19:28 +00:00Commented Mar 27, 2020 at 14:19