# Anomalous Curves Part 1: Don't be clever with your elliptic curve order

$$ \def\F{\mathbb{F}} $$

Have you ever been confused by the numbers $p,q,r$ in a paper dealing with elliptic curves? Some paper use $q$ for the order of the elliptic curve over a field of order $p$. Conveniently, other papers use the **exact opposite notation**, while some get original and use $r$ for the field size, or the order of a subgroup of the curve, or something else…

What if I told you there are curves where $p=q=r$? We could decide to only use these curves and never have to go back on page 2 of a paper to see what are $p,q$ or $r$!

Joke aside, these curves actually exist and go by the name of **anomalous curves**, that is, curves $E(\mathbb{F}_p)$ with $\# E(\F_p)=p$. If you know Hasse’s Theorem, you’ll understand why these curves are also called *curves of trace one*.

Here is an example:

```
E: y^2 = x^3 + 425706413842211054102700238164133538302169176474*x + 203362936548826936673264444982866339953265530166
p = 730750818665451459112596905638433048232067471723
```

Regardless of my rant on inconsistent notations for elliptic curves, using such curves could result in more elegant notation, or even a *Nothing up my sleeve* mechanism for choosing elliptic curves. Moreover, they could be use to derive efficient *recursive proof systems* without having to use cycles of elliptic curves.

It turns out that these curves are actually **totally worthless for cryptography.** Namely, the discrete logarithm problem can be solved in $O(\log p)$ on these curves. So these curves are secure only if their field arithmetic is intractable. Clearly not ideal.

This was discovered independently by Smart and Semaev in 1998-99.

In a coming series of posts, I will try to explore how these attacks work. I think they use some interesting math that is not commonly used in current cryptographic schemes.

For example, in pairing-based cryptography, we regularly use a field extension $\F_p \subset \F_{p^k}$ to, for example, capture the torsion points. In Smart’s attack, we use a dual of some kind; we look at a map $E(\mathbb{Q}_p) \to \tilde{E}(\F_p)$ and lift points over $\F_p$ to points over $\mathbb{Q}_p$. In the next post, I’ll explain what this means and how to use it to break ECDLP.