Why does Smart's attack only work on anomalous curves?

Question

Nigel Smart's attack solves the discrete logarithm problem in linear time. It requires the curve, however, to be anomalous, i.e. to have a trace of Frobenius equal to one or, equivalently, to be of the same order as the underlying field, $\#E=p$.

Smart's paper is here: http://www.hpl.hp.com/techreports/97/HPL-97-128.html

I'm trying to understand why it doesn't work for other curves? I'm guessing that it has something to do with the properties of the p-adic logarithm but I can't quite put my finger on it.

Any hint or explanation will be appreciated.

Answer 1

You can find an answer at section 5.4 of Washington's Elliptic Curves: Number Theory and Cryptography.

Following their notation (and skipping the technical details about reduction $\mod p$ and $E_r$ subgroups), let $N=\#E$ and assume $p\nmid N$. Let $\ell_1=\lambda_1(N\tilde P)$, $\ell_2=\lambda_1(N\tilde Q)$, so that $k\equiv \ell_2/\ell_1 \mod p$ (we want to prove this). Set also $\tilde K = k\tilde P-\tilde Q$. We have

$$k\ell_1 - \ell_2=\lambda_1(kN\tilde P-N\tilde Q)=\lambda_1(N\tilde K)\equiv N\lambda_1(\tilde K) \mod p.$$

In the last step you cannot continue, because the initial assumption makes $N$ invertible $\mod p$ and you can't say that this equals $0$, failing to prove that $k\equiv \ell_2/\ell_1 \mod p$. You can see that this proof does work if $p$ divides $N$.

To my understanding, this would mean that if $p$ divides the number of points, then you may also perform the attack, but I haven't read enough on it to confirm this.

Answer 2

Do see the paper https://articles.math.cas.cz/10.21136/CMJ.2018.0128-17 Also freely downloadable at https://arxiv.org/abs/1702.07107 See detailed explanation https://www.slideshare.net/PadmaGadiyar/discrete-logarithm-problem-over-prime-fields-noncanonical-lifts-and-logarithmic-derivative