Cryptography Reference
In-Depth Information
F
q
and if one has an efficiently computable isomorphism
ψ
:
→
P
G
where
G
is another group, then the ECDLP instances in
can be efficiently reduced to
instances of the DLP in
G
because, since the isomorphism preserves scalar multipli-
cation, given another point
Q
P
∈
P
one simply has to compute:
log
P
Q
=
log
)
ψ(
Q
).
ψ(
P
The first attack of this kind arose in 1993, when Menezes, Okamoto and Vanstone
presented what is now known as the MOV attack or MOV reduction. This attack
applied originally to the class of supersingular curves but was later extended to
apply to all elliptic curves of small embedding degree in the sense of the definition
below.
Definition 11.4
Let
F
q
be a finite field,
E
an elliptic curve over
F
q
, and
n
adivisor
of
1. Then the
embedding degree
of
E
with respect
to
n
is the smallest integer
k
such that
n
|
E
(
F
q
)
|
such that gcd
(
n
,
q
)
=
q
k
|
−
1.
Z
n
and so
k
is simply the order
(
,
)
=
Note that, since gcd
n
q
1,
q
mod
n
belongs to
Z
n
, namely, the smallest positive integer such that
q
k
of this element in
≡
1
(
mod
n
)
.
Suppose now that
n
is the prime order of a point
P
∈
E
(
F
q
)
and gcd
(
n
,
q
)
=
1.
F
q
k
is cyclic of order
q
k
Then the multiplicative group of the field
−
1 (Corollary
⊆ F
q
k
such that
2.5) and, since
n
divides it, there is a unique subgroup
G
|
G
|=
n
(Exercise 2.12). Then, under the additional assumption that
gcd
(
n
,
q
−
1
)
=
1,
the MOV reduction constructs an isomorphism from
to
G
by using the
We i l
pairing
(see Chap.
10
for the general definition of pairings). There is another similar
attack, called the Frey-Rück attack or FR reduction, that also constructs such an
isomorphism without requiring the additional constraint that gcd
P
1. The
FR reduction is based on another pairing, namely the
Tate pairing
(also called the
Tate-Lichtenbaum pairing
).
It is interesting to point out that both pairings play a relevant role in elliptic curve
cryptography, not only because of these attacks, which are often called 'destructive
applications' of pairings but, more importantly, because of their constructive appli-
cations in other aspect of elliptic curve cryptography, namely, the construction of
IBE schemes. The study of these pairings is beyond the scope of this topic and we
refer to the excellent presentations in [181, 197], and in particular to [181, XI.6]
and [197, 5.3], for elliptic curve pairings and pairing-based attacks on the ECDLP.
A more elementary introduction to pairings and their cryptographic applications is
contained in [102] and more advanced presentations are contained in [26, 53], with
the latter including also detailed information on pairing implementation.
A necessary condition for these attacks to be viable is that the embedding degree
not be too high. The most optimistic estimates for the subexponential running time
that can be expected for an index calculus method over
(
n
,
q
−
1
)
=
F
q
k
mean that this time
ln
2
q
, and Balasubramanian and Koblitz [8]
proved that for most randomly generated elliptic curves we have an embedding
degree
k
becomes fully exponential for
k
≥
ln
2
q
(and that, in fact, for most of these curves the embedding degree is
>
