Cryptography Reference
In-Depth Information
Let
E
be an elliptic curve over
K = F
q
n
and let
k = F
q
. The function field of
E
is
K
(
E
).
The idea (called in this setting a
covering attack
) is to find a curve
C
over
K
such that
K
(
C
) is a finite extension of
K
(
E
) (so that there is a map
C
→
E
of finite degree) and such
that there is an automorphism
σ
of degree
n
on
K
(
C
) extending the
q
-power Frobenius so
(
C
0
) for some curve
C
0
. The composition of the
that the fixed field of
K
(
C
) under
σ
is
k
)toPic
C
(
) and the norm map from Pic
C
(
)toPic
C
0
(
conorm map from
E
(
K
K
K
k
) transfers
)toPic
C
0
(
the DLP from
E
(
). Hence, as long as the composition of these maps is not
trivial, then one has reduced the DLP from
E
(
K
k
) to the divisor class group of a curve
C
0
K
over
. One can then solve the DLP using an index calculus algorithm, which is feasible if
the genus of
C
0
is not too large.
A variant of the Weil descent concept that avoids function fields and divisor class groups
is to perform index calculus directly on Abelian varieties. This variant is the subject of the
following section.
k
15.8 Discrete logarithms on elliptic curves over extension fields
We now discuss some related algorithms, which can be applied to elliptic curves over
extension fields. We start by recalling Semaev's idea of summation polynomials.
15.8.1 Semaev's summation polynomials
Suppose that
E
is an elliptic curve defined over a prime field
F
p
, and that elements of
F
p
are represented as integers in the interval [0
,p
−
1]. Semaev [
486
] considered a factor base
p
1
/n
≤
≤
}
B
={
(
x,y
)
∈
E
(
F
p
):0
x
p
1
/n
.
Semaev hoped to perform an index calculus algorithm similar to the one in Section
15.5.1
.
For random points
R
for some fixed integer
n
≥
2. Note that #
B
≈
=
[
a
]
P
+
[
b
]
Q
the task is to write
R
as a sum of points in
B
.To
accomplish this, Semaev introduced the notion of a summation polynomial.
Definition 15.8.1
Let
E
:
y
2
x
3
=
+
a
4
x
+
a
6
be an elliptic curve defined over
F
q
, where
the characteristic of
F
q
is neither 2 nor 3 (this condition can be avoided). The
summation
polynomials
Summ
n
∈ F
q
[
x
1
,x
2
,...,x
n
]for
n
≥
2 are defined as follows:
Summ
2
(
x
1
,x
2
)
=
x
1
−
x
2
.
x
2
)
2
x
3
−
a
4
)
2
Summ
3
(
x
1
,x
2
,x
3
)
=
(
x
1
−
2((
x
1
+
x
2
)(
x
1
x
2
+
a
4
)
+
2
a
6
)
x
3
+
((
x
1
x
2
−
−
4
a
6
(
x
1
+
x
2
)).
Summ
n
(
x
1
,x
2
,...,x
n
)
≥
4 where
R
x
(
F,G
) is the resultant of the polynomials
F
and
G
with respect to the
variable
x
.
=
R
x
(Summ
n
−
1
(
x
1
,...,x
n
−
2
,x
)
,
Summ
3
(
x
n
−
1
,x
n
,x
)) for
n
