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?

The security of the Diffie-Hellman protocol relies on the decisional Diffie-Hellman assumption. This assumption, in turn, requires the discrete-logarithm problem (DLP) to be hard. 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 Apr 14 '20 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 Apr 14 '20 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 Apr 14 '20 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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