Revisiting Discrete Logarithm Reductions

A reduction showing that the hardness of the discrete logarithm (DL) assumption implies the hardness of the computational Diffie-Hellman (CDH) assumption, given a suitable auxiliary input as advice, was first presented by den Boer [Crypto, 88]. We consider groups of prime order p, where p-1 is somewhat smooth (say, every prime q that divides p-1 is less than 2 100 ). Several practically relevant groups satisfy this condition. 1. We present a concretely efficient version of den Boer's reduction for such groups. In particular, among practically relevant groups, we obtain the most efficient and tightest reduction in the literature for BLS12-381, showing that DL = CDH. 2. By generalizing den Boer's reduction, we show that in these groups the n-Power DL (n-PDL) assumption implies n-Diffie-Hellman Exponent (n-DHE) assumption, where n is polynomial in the security parameter. On the negative side, we show there is no generic reduction, which could demonstrate that n-PDL implies the n-Generalized Diffie-Hellman Exponent (n-GDHE) assumption. This is in stark contrast with the algebraic group model, where this implication holds.