Cryptography Reference
In-Depth Information
Theorem 26.4.1
Let E be an elliptic curve over
F
q
and let r be a prime dividing
#
E
(
F
q
)
.
Suppose that r
(
q
−
1)
and that
gcd(
r,q
)
=
1
. ThenE
[
r
]
⊂
E
(
F
q
k
)
if and only if r divides
(
q
k
−
1)
.
Proof
See [
25
].
Balasubramanian and Koblitz also show that a “random” curve is expected to have very
large embedding degree. Hence, the MOV/FR attack is not a serious threat to the ECDLP on
randomly chosen elliptic curves. However, as noted by Menezes, Okamoto and Vanstone,
supersingular elliptic curves are always potentially vulnerable to the attack.
Theorem 26.4.2
Let E be a supersingular elliptic curve over
F
q
and suppose r
|
#
E
(
F
q
)
.
Then the embedding degree k
(
q,r
)
is such that k
(
q,r
)
≤
6
.
Proof
See Corollary
9.11.9
.
26.4.1 Anomalous curves
F
p
with
p
points (such curves
are called
anomalous elliptic curves
) can be efficiently solved. This was first noticed by
Semaev [
484
] and generalised to higher genus curves by R uck [
455
]. We present their
method in this section. An alternative way to view the attack (using
p
-adic lifting rather
than differentials) was given by Satoh and Araki [
460
] and Smart [
511
].
The theoretical tool is an observation of Serre [
487
].
The discrete logarithm problem on elliptic curves over
Lemma 26.4.3
Let P
∈
E
(
F
p
)
have order p. Let f
P
be a function in
F
p
(
E
)
with
div(
f
P
)
=
p
(
P
)
−
p
(
O
E
)
. Then the map
df
P
f
P
P
→
is a well-defined group homomorphism from E
(
F
p
)[
p
]
to
F
p
(
E
)
.
Proof
First note that
f
P
is defined up to a constant, and that
d
(
cf
P
)
/
(
cf
P
)
=
df
P
/f
P
.
Hence, the map is well-defined.
Now let
Q
=
[
a
]
P
and let
f
P
be as in the statement of the lemma. Then there is a
function
g
such that
div(
g
)
=
(
Q
)
−
a
(
P
)
+
(
a
−
1)(
O
E
)
.
One has
div(
g
p
f
P
)
=
p
div(
g
)
+
a
div(
f
P
)
=
p
(
Q
)
−
ap
(
P
)
+
p
(
a
−
1)(
O
E
)
+
ap
(
P
)
−
ap
(
O
E
)
=
p
(
Q
)
−
p
(
O
E
)
.
