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?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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
answered Apr 13 '20 at 23:41
-
$\begingroup$ Are there any threshold for the size of the characteristics? $\endgroup$ – kelalaka Apr 14 '20 at 14:15
-
2
-
$\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
