The Discrete Logarithm Problem - Elliptic Curves: Number Theory and Cryptography - page 158

5.4 Anomalous Curves

The reason the MOV attack works is that it is possible to use the Weil
pairing. In order to avoid this, it was suggested that elliptic curves E over F q
with

# E ( F q )= q

be used. Such curves are called anomalous . Unfortunately, the discrete log
problem for the group E ( F q ) can be solved quickly. However, as we'll see be-
low, anomalous curves are potentially useful when considered over extensions
of F q , since they permit a speed-up in certain calculations in E ( F q ).
The Weil pairing is not defined on E [ p ] (or, if we defined it, it would be
trivial since E [ p ] is cyclic and also since there are no nontrivial p th roots of
unity in characteristic p ; however, see [10] for a way to use a Weil pairing in
this situation). Therefore, it was hoped that this would be a good way to
avoid the MOV attack. However, it turns out that there is a different attack
for anomalous curves that works even faster for these curves than the MOV
attack works for supersingular curves.
Inthefollowing,weshowhowtocomputediscretelogsinthecase q = p .
Procedures for doing this have been developed in [95], [102], and [115]. Similar
ideas work for subgroups of p -power order in E ( F q )when q is a power of p
(but in Proposition 5.6 we would need to lift E to a curve defined over a larger
ring than Z ).
Warning: The property of being anomalous depends on the base field.
If E is anomalous over F q , it is not necessarily anomalous over any F q n for
n ≥ 2. See Exercises 5.5 and 5.6. This is in contrast to supersingularity,
which is independent of the base field and is really a property of the curve
over the algebraic closure (since supersingular means that there are no points
of order p with coordinates in the algebraic closure of the base field).

The first thing we need to do is lift the curve E and the points P, Q to an
elliptic curve over Z .

PROPOSITION 5.6
Let E be an elliptic curve over F p and let P, Q

∈ E ( F p ) .

W e assu m e

E isinWe erstra ss form y 2 = x 3 + Ax + B .Then here exist integers

A, B, x 1 ,x 2 ,y 1 ,y 2 and an ellipticcurve E given by

Ax + B

y 2 = x 3 +

su ch that P =( x 1 ,y 1 ) ,

Q =( x 2 ,y 2 ) E ( Q ) and such that

∈

A, B, P, Q

A ≡ B ≡ P ≡ Q≡ (mod p ) .