In this paper we compare hardness of two well known problems: the Diffie-Hellman problem and the root finding problem. We prove that in any cyclic group computing Diffie-Hellman is not weaker than root finding if certain circumstances are met. As will be discussed in the paper this theorem can affect many branches of public-key cryptography especially on proving the security of cryptographic protocols in hidden-order groups. For examples of such effects we discuss effects of the new theorem on:
1. Proving the security of cryptosystems based on class groups of imaginary quadratic orders (IQ-cryptosystems),
2. Proving the hardness of the Composite Diffie-Hellman problem and security of its related cryptosystems.
In the concept of IQ-cryptography, root finding is supposed to be a hard problem, but there is no significant argument about the hardness of Diffie-Hellman. By applying the new theorem we prove the hardness of computing Diffie-Hellman in class groups of imaginary quadratic orders, and then we construct a new IQ-cryptosystem and prove that it is hard to break.
There are two significant theorems about intractability of the composite Diffie-Hellman. One of them was proved by Shmuely in 1985 and the other, which is stronger, by Azimian, Mohajeri, and Salmasizadeh in 2005. As will be shown in this paper, both of theorems can be driven by applying the new theorem. We also construct a new public-key scheme based on the composite Diffie-Hellman and prove that it is provably secure based on intractability of factoring.