Cryptography Reference
In-Depth Information
For many more details see Section 3 of [
163
]. The following result is from [
486
].
Theorem 15.8.2
Summation polynomials have the following properties:
n
q
is a
ro
ot of
Summ
n
if and only if there exists
(
y
1
,...,y
n
)
n
q
such
(
x
1
,...,x
n
)
∈ F
∈ F
F
q
)
and
i
=
1
P
i
=∞
that P
i
=
(
x
i
,y
i
)
∈
E
(
.
Summ
n
is symmetric.
The degree of
Summ
n
in x
i
is
2
n
−
2
.
Exercise 15.8.3
Prove Theorem
15.8.2
.
n
to
One way to decompose
R
=
(
x
R
,y
R
)in
B
is to find solutions (
x
1
,...,x
n
)
∈ Z
p
1
/n
.
Summ
n
+
1
(
x
1
,x
2
,...,x
n
,x
R
)
≡
0(mod
p
)
,
such that 0
≤
x
i
≤
(15.12)
If such a solution exists and can be found then one finds the corresponding
y
-coordinates
±
y
i
. Suppose that each
y
i
∈ F
p
. Then each
P
i
=
(
x
i
,y
i
)isin
B
and by Theorem
15.8.2
there exist
s
i
∈{−
R
. The sign bits
s
i
can be found
by exhaustive search, thereby yielding a relation. Since #
1
,
1
}
such that
s
1
P
1
+···+
s
n
P
n
=
{
P
1
+
P
2
+···+
P
n
:
P
i
∈
B
}≈
(
p
1
/n
)
n
/n
!
p/n
! the expected number of points
R
that have to be selected before a
relation is obtained is about
n
!.
Unfortunately, no efficient algorithm is known for solving the polynomial equa-
tion (
15.12
)evenfor
n
=
5 (in which case the equation has degree 16 in each of its 5
variables). Coppersmith's method (see Section
19.2
) seems not to be useful for this task.
In reference to the remarks of Section
15.2.3
we see that all requirements for an index
calculus algorithm are met, except that it is not efficient to decompose a smooth element
over the factor base.
=
15.8.2 Gaudry's variant of Semaev's method
Gaudry [
225
] realised that it might be possible to take roots of summation polynomials if one
is working with elliptic curves over extension fields. Gaudry's algorithm may be viewed as
doing Weil descent without divisor class groups. Indeed, the paper [
225
] presents a general
approach to index calculus on Abelian varieties and so the results apply in greater generality
than just Weil descent of elliptic curves.
Suppose that
E
is an elliptic curve defined over a finite field
F
q
n
with
n>
1. Gaudry [
225
]
defines a factor base
B
={
(
x,y
)
∈
E
(
F
q
n
):
x
∈ F
q
}
so that #
F
q
-rational points on the algebraic set
F
formed by intersecting the Weil restriction of scalars of
E
with respect to
B
≈
q
. Gaudry considers this as the set of
F
q
n
/
F
q
by
n
1) as in
Lemma
5.7.1
. If the algebraic set
F
is irreducible then it is a one-dimensional variety
F
.
−
1 hyperplanes
V
(
x
i
)for2
≤
i
≤
n
, where
x
=
x
1
θ
1
+···+
x
n
θ
n
(with
θ
1
=
