Cryptography Reference
In-Depth Information
For the analysis one needs to estimate the probability that a randomly chosen reduced
divisor is smooth.
Theorem 15.6.1
(Theorem 6 of Enge and Stein [
183
]) Let C be a hyperelliptic curve of
genus g over
F
q
. Let c>
1
and let b
=
log
q
(
L
q
g
(1
/
2
,c
))
. Then the number of b-smooth
reduced divisors of degree g is at least
q
g
L
q
g
(1
/
2
,
1
/
(2
c
)
+
o
(1))
for fixed q and g
→∞
.
Note that the smoothness bound in the above result is the ceiling of a real number.
Hence one cannot deduce subexponential running time unless the genus is sufficiently
large compared with the field size.
15.6.1 Index calculus on hyperelliptic curves
#Pic
0
F
q
(
C
) and
r
2
Suppose that
r
|
N
=
N
. Suppose
D
1
,D
2
are two divisor classes on
C
over
F
q
of order
r
represented by reduced divisors
D
1
and
D
2
. The algorithm of
Section
15.5.1
immediately applies to solve the DLP: choose the factor base as above; gen-
erate random reduced divisors by computing [
n
1
]
D
1
+
[
n
2
]
D
2
+
δ
(where
δ
is uniformly
Pic
0
chosen
9
from the subgroup
G
⊆
F
q
(
C
) of order
N/r
); store the resulting smooth rela-
tions; perform linear algebra modulo
r
to find integers
a,b
such that [
a
]
D
1
+
0
(extra care is needed when there are two points at infinity to be sure the relation is correct).
[
b
]
D
2
≡
Exercise 1
5.
6.2
Show that the expected running time of this algorithm is (rigorously!)
L
q
g
(1
/
2
,
√
2
+
o
(1)) bit operations as
g
→∞
.
We refer to Section VII.5 of [
61
] for practical details of the algorithm. Note that the
performance can be improved using the sieving method of Flassenberg and Paulus [
189
].
15.6.2 The algorithm of Adleman, De Marrais and Huang
This algorithm, from [
4
], uses the same factor base as the method of the previous section. The
main difference is to generate relations by decomposing principal divisors
A
(
x
)
+
yB
(
x
).
An advantage of this approach is that group operations are not required.
By Exercise
10.1.21
it is easy to compute
v
P
(
A
(
x
)
+
yB
(
x
)) by computing the norm
A
(
x
)
2
F
(
x
)
B
(
x
)
2
−
H
(
x
)
A
(
x
)
B
(
x
)
−
and factoring it as a polynomial. If deg(
A
(
x
))
=
d
A
<g
and deg(
B
(
x
))
=
d
B
<g
then the norm has degree at most max
{
2
d
A
,
(
g
+
1)
+
d
A
+
, which is much larger in general than the degree
g
polynomial in
a reduced Mumford representation, but still
O
(
g
) in practice.
We need to make the heuristic assumption that the probability the norm is
b
-smooth is
the same as the probability that a random polynomial of the same degree is
b
-smooth. We
d
B
,
2
g
+
2
+
2
d
B
}
9
We assume that generators for this group are known so that it is easy to sample uniformly from this group.
