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.

  • $\begingroup$ This was cross-posted on StackOverflow. Please don't do that. You should pick one site and stick with it. $\endgroup$
    – mikeazo
    Nov 1 '17 at 0:45

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.


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.