On the complexity of breaking the Diffie-Hellman protocol
Ueli M. Maurer, Stefan Wolf · Repository for Publications and Research Data (ETH Zurich) · 1996
It is shown that for a class of nite groups, breaking the Die-Hellman protocol is polynomial-time equivalent to computing discrete logarithms.Let G be a cyclic group with generator g and order jGj whose prime factorization is known.When for each large prime factor p of jGj an auxiliary group H p dened over GF (p) with smooth order is given, then breaking the Die-Hellman protocol for G and computing discrete logarithms in G are polynomial-time equivalent.Possible auxiliary groups H p are elliptic curves over GF (p) or over an extension eld of GF (p), certain subgroups of the multiplicative group of such an extension eld, and the Jacobian of a hyperelliptic curve.For a list of expressions in p, including p ; 1, p + 1 , and the cyclotomic polynomials of low degree in p, it is shown that an appropriate group H p can eciently be constructed if one of the expressions in the list is smooth.Furthermore, ecient constructions of Die-Hellman groups with provable equivalence are described.