0
$\begingroup$

Mathematical hardness assumptions like that of the factoring problem, the RSA problem, and the discrete log problem all straightforwardly lead to one-way functions. But what about the computational Diffie-Hellman (CDH) problem?

My question is, what one-way functions have been constructed based on assuming the hardness of CDH?

All I've come across are this paper, which constructs a trapdoor one-way function based on assuming the hardness of CDH, but the construction is rather complicated. Is there a simpler construction which just gives one-wayness, even if there's no trapdoor?

$\endgroup$
4
  • $\begingroup$ If CDH is hard in a group then discrete log is hard in that group, so exponentiation is one-way. $\endgroup$
    – Mikero
    Oct 31, 2020 at 5:38
  • $\begingroup$ @Mikero But is there any one-way function that the hardness of CDH proves but the hardness of discrete log does not? $\endgroup$ Oct 31, 2020 at 6:03
  • $\begingroup$ You initially asked "what one-way functions have been constructed based on assuming the hardness of CDH?", and Mikero pointed that exponentiation fits that definition. Is the real question that in the above comment? Prove that the answer is no using Mikero's comment. $\endgroup$
    – fgrieu
    Oct 31, 2020 at 8:36
  • $\begingroup$ I'm guessing what you mean to ask is: can you define a function that is one way if and only if CDH holds in that group? $\endgroup$
    – Mikero
    Oct 31, 2020 at 16:26

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.