Ueli Maurer and Stefan Wolf
This paper consists of three parts. First, various types of Diffie-Hellman oracles for a cyclic group $G$ and subgroups of $G$ are defined and their equivalence is proved. In particular, the security of using a subgroup of $G$ instead of $G$ in the Diffie-Hellman protocol is investigated. Second, we derive several new conditions for the polynomial-time equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms in $G$ which extend former results by den Boer and Maurer. Finally, efficient constructions of Diffie-Hellman groups with provable equivalence are described.