I Google around and can't find any page mentioning Diffie-Hellman with Galois field $GF(p^n)$ with $n>1$.

  • Is there a reason for this?
  • For example, wouldn't Diffie-Hellman with $GF(2^n)$ be desirable for computation?

1 Answer 1


The security of the Diffie-Hellman protocol relies on the Decisional Diffie-Hellman assumption, which is a stronger assumption than the Discrete-Logarithm Problem (DLP). In an earlier line of works, heuristic quasi-polynomial algorithms were shown for fields with small characterstic [J,BGJT,GKZ]. A proof (for expected run-time) was recently given by Wesolowski and Kleinjung [WK]. In particular, it was shown that DLP in $\mathbf{F}_{p^n}^\times$ can be solved in (expected) time $(pn)^{O(\log{n})}$. In light of these attacks, the Diffie-Hellman protocol should be avoided in fields of small characteristic.

[J] Joux, A new index calculus algorithm with complexity L(1/4+o(1)) in very small characteristic

[BGJT] Barbulescu et al., A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic

[GKZ] Granger, Kleinjung and Zumbrägel, On the discrete logarithm problem infinite fields of fixed characteristic

[WK] Wesolowski and Kleinjung Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic

  • $\begingroup$ Are there any threshold for the size of the characteristics? $\endgroup$
    – kelalaka
    Commented Apr 14, 2020 at 14:15
  • 2
    $\begingroup$ @kelalaka: we recently had a question touching that, the link in comment is an interesting article by our favorite bear. $\endgroup$
    – fgrieu
    Commented Apr 14, 2020 at 14:27
  • $\begingroup$ Thanks for this answer. I had always assumed that DH was done in $GF(2^m)$, partly because squaring is easy and makes it easy to exponentiate. $\endgroup$
    – Evariste
    Commented Apr 14, 2020 at 16:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.