Are there any standard (or at least well-know) elliptic curves over $F_{p^4}$ where $p$ is a ~64-bit prime? I know Microsoft has FourQ curve which works over $F_{p^2}$ where $p$ is a 127-bit prime, but I haven't come across any curve that works over extensions of ~64-bit fields.

If there are no standard/well-know curves that fit this, are there any fundamental reasons for why elliptic curves over $F_{p^4}$ would not be a good idea?

  • $\begingroup$ Minor nit: for FourQ, $p$ is a 127 bit prime... $\endgroup$ – poncho Mar 2 at 19:11
  • $\begingroup$ Thanks! Updated. $\endgroup$ – irakliy Mar 2 at 19:20
  • $\begingroup$ There is an algorithm running in $\tilde{O}(p^{2-2/n})$, details in this paper. In your case, $n$ is $4$ so it runs faster than generic methods to solve the discrete logarithm problem. $\endgroup$ – corpsfini Mar 2 at 19:35
  • $\begingroup$ So - does this mean that a curve over $F_{p^4}$ would have about 96 bit security level? Also, does this affect FourQ curve in the same way? $\endgroup$ – irakliy Mar 2 at 20:45
  • $\begingroup$ The attack would still be mostly impracticable since it would require a lot of memory. FourQ is over a field $\mathbf F_{p^2}$, and the attack on the paper does not reduce the security compared to generic algorithms. $\endgroup$ – corpsfini Mar 3 at 11:59

Your Answer

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

Browse other questions tagged or ask your own question.