Cryptography Reference
In-Depth Information
Hence, the number of oracle queries in the first line of the table in Theorem
21.4.10
can be
reduced to
O
(log(
r
) log log(
r
)). As mentioned in Remark
13.3.2
one cannot use the BSGS
algorithm with projective coordinates, as the non-uniqueness of the representation means
one cannot efficiently detect a match between two lists.
Exercise 21.4.12
Generalise the Maurer algorithm to the case where the group of points
on the elliptic curve is not necessarily cyclic. Determine the complexity if
l
1
is the largest
prime for which
E
(
F
r
)[
l
1
] is not cyclic and
l
2
is the largest prime dividing #
E
(
F
r
)forwhich
E
(
F
r
)[
l
2
] is cyclic.
1 is smooth then one can use the algebraic group
G
2
,r
= T
2
(
Exercise 21.4.13
If
r
+
F
r
)
(see Section
6.3
) instead of
G
m
(
F
r
)or
E
(
F
r
). There are two approaches: the first is to use
the usual representation
{
a
+
bθ
∈ F
r
2
:N
F
r
2
/
F
r
(
a
+
bθ
)
=
1
}
for
G
2
,r
and the second is
1
(
to use the representation
corresponding to the map decomp
2
from
Definition
6.3.7
. Determine the number of (perfect) oracle queries in the reductions from
Fixed-CDH to DLP for these two representations. Which is better? Repeat the exercise
when one has a CDH oracle.
A
F
r
)for
T
2
(
F
r
)
−{
1
}
Corollary 21.4.14
Let c
∈ R
>
1
. Let
(
G
n
,g
n
,r
n
)
be a family of groups for n
∈ N
where
g
n
∈
G
n
has orderr
n
andr
n
is ann-bit prime. Suppose we are given
auxiliary elliptic curves
(
E
n
,N
n
)
for the family, where E
n
is an elliptic curve over
F
r
n
such that
#
E
n
(
F
r
n
)
=
N
n
and
N
n
is O
(log(
r
n
)
c
)
-smooth. Then the DLP in
g
n
is equivalent to the Fixed-CDH problem
in
g
n
.
Exercise 21.4.15
Prove Corollary
21.4.14
.
We now state the conjecture of Maurer and Wolf that all Hasse intervals contain a polyn
o
-
mially smo
ot
h integer. Define
ν
(
r
) to be the minimum, over all integers
n
2
√
r,
∈
[
r
+
1
−
2
√
r
], of the largest prime divisor of
n
. Conjecture 1 of [
367
] states that
r
+
1
+
log(
r
)
O
(1)
.
ν
(
r
)
=
(21.9)
See Remark
15.3.5
for discussion of this. Muzereau, Smart and Vercauteren [
402
] note that
if
r
is a pseudo-Mersenne prime (as is often used in elliptic curve cryptography) then the
Hasse interval usually contains a power of 2. Similarly, as noted by Maurer and Wolf in
[
365
], one can first choose a random smooth integer
n
and then search for a prime
r
close
to
n
and work with a group
G
of order
r
.
Exercise 21.4.16
Show how to use the algorithm of Section
19.4.4
to construct a smooth
integer in the Hasse interval. Construct a 2
40
-smooth integer (not equal to 2
255
) close to
p
2
255
=
−
19 using this method.
Remark 21.4.17
There are two possible interpretations of Corollary
21.4.14
. The first
interpretation is: if there exists an efficient algorithm for CDH or Fixed-CDH in a group
G
F
r
with
sufficiently smooth order then there exists an efficient algorithm to solve the DLP in
G
.
=
g
of prime order
r
and if there exists an auxiliary elliptic curve over
