0
$\begingroup$

I am aware that when the equation $\#E(\mathbb{Z}_p) = p$ holds for prime $p$, the elliptic curve is called "anomalous" and is insecure do to "Smart's attack".

Consider the similar case that $E(\mathbb{Z}_p)$ has a proper subgroup of (prime) order $p$, so $p \neq \#E$. In this case $p$ divides $\#E$ and $\#E > p$. This relationship of the (sub)group order matching the field size (thus forcing primality) is desirable for some applications.

Is such a curve secure for the discrete log performed in the $p$-order subgroup, or is this vulnerable to a similar attack? What would be the process to generate such a curve that is arguably safe for cryptographic use?

From what I read, curves over $GF(2^n)$ for some $n$ are less stable. But analogously, for $E(GF(2^n))$ there could be a subgroup of order $2^n$ and as long as $2^n$ has a large prime factor it should be safe for the discrete log. Is this also a possibility?

$\endgroup$
  • $\begingroup$ "As long as $2^n$ has a large prime factor" - $2^n$ never has a large prime factor... $\endgroup$ – poncho Aug 13 at 14:38
1
$\begingroup$

It seems that curves like that do not exist.

Hasse's bound states that $|N-(p+1)| \le 2\sqrt p$, where $N=\#E$. Writing the order of the group as $N = ph$, you get:

$|ph-(p+1)| \le 2\sqrt p \rightarrow$

$|p(h-1)-1)| \le 2\sqrt p \rightarrow$

$|\sqrt p(h-1)-\frac{1}{\sqrt p}| \le 2$

The only way this inequality is true for $p > 5$ is if $h = 1$, i.e., $\#E=p$.

$\endgroup$
  • 2
    $\begingroup$ The curve $y^2=x^3+3x$ over $\mathbb F_5$ has $10$ rational points. (This is the only counterexample.) $\endgroup$ – yyyyyyy Aug 13 at 13:03

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.