-1
$\begingroup$

Suppose I have an elliptic curve defined over a prime field $\operatorname{GF}(p)$ where $p$ is a large prime (e.g. 256-bit). Suppose also that $p = kn +1$, where $n$ is a relatively large power of $2$ (e.g. $2^{32}$). This structure implies that $\operatorname{GF}(p)$ has $n^{\mathit{th}}$ roots of unity.

My question is: does the fact that $\operatorname{GF}(p)$ has "high order" roots of unity make curves defined over this field inherently less secure?

$\endgroup$
1
$\begingroup$

My question is: does the fact that $\operatorname{GF}(p)$ has "high order" roots of unity make curves defined over this field inherently less secure?

Not particularly; the factorization of $p-1$ is not specifically relevant to the strength of a curve over $\operatorname{GF}(p)$.

Now, it is quite relevant to the strength of the group $\mathbb{Z}_p^*$; however that's because the order of the group is always $p-1$ (assuming $p$ is prime), and the factorization of the group order is quite relevant. However, the elliptic curve (in general) doesn't have order $p-1$; instead, it is $p + \delta$ for some $|\delta| < 2\sqrt{p}$ (the exact value of $\delta$ depends on the precise curve you pick), and it is the factorization of $p + \delta$ which is important.

$\endgroup$
  • $\begingroup$ Thank you! Quick follow-up: are there any well-known or well-studied curves defined over such prime fields? All curves I've seen so far seem to be defined over prime fields with very small roots of unity. $\endgroup$ – irakliy May 20 at 19:01
  • 1
    $\begingroup$ @irakliy: there's the NIST curve P-224, which has $p = 2^{224} - 2^{96} + 1$; that certainly has high roots of unity for large powers of 2. BTW: why is that important to you? $\endgroup$ – poncho May 20 at 19:26
  • $\begingroup$ I've been looking into STARKs. When implementing them over a prime field, the field must have large roots of unity (otherwise computations become prohibitively expensive). The underlying reason is that STARKs require a lot of polynomial interpolations and multi-point evaluations which can be done efficiently using FFT over a domain consisting of roots of unity. $\endgroup$ – irakliy May 20 at 19:50

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.