Cryptography Reference
In-Depth Information
Remark 13.3.2
When solving the DLP it is natural to implement the group operations
as efficiently as possible. For example, when using elliptic curves it would be tempting
to use a projective representation for group elements (see Exercise
13.1.2
). However this
is not suitable for the BSGS method (or the rho and kangaroo methods) as one cannot
efficiently detect a match
y
∈
L
when there is a non-unique representation for the group
element
y
.
Exercise 13.3.3
On average, the BSGS algorithm finds a match after half the giant steps
have been performed. The av
e
rage-case running time of the algorithm as presented is
therefore approximately 1
.
5
√
r
group opera
tio
ns. Show how to obtai
n an
algorithm that
requires, in the average case, approximately
√
2
r
group operations and
√
r/
2 group elements
of storage.
Exercise 13.3.4
(Pollard [
438
]) A variant of the BSGS algorithm is to compute the baby
steps and giant steps in parallel, storing the points together in a single structure. Show that if
x
and
y
are chosen uniformly in the interval [0
,r
]
}
is approximately
3
r
. H
e
nce, show that the average-case running time of this variant of the
BSGS algorithm is
∩ Z
then the expected value of max
{
x,y
3
√
r
group operations.
4
Exercise 13.3.5
Design a variant of the BSGS
m
ethod that requires
O
(
r/M
) group opera-
tions if the available storage is only for
M<
√
r
group elements.
Exercise 13.3.6
(DLP in an interval)
Suppose one is given
g
of order
r
inagroup
G
and integers 0
≤
b,w <r
. The DLP in an interval of length
w
is: given
h
∈
g
such that
g
a
for some
b
h
=
≤
a<b
+
w
to find
a
. Give a BSGS algorithm to find
a
in average-case
√
2
w
group operations and
√
w/
2 group elements of storage.
Exercise 13.3.7
Suppose one considers the DLP in a group
G
where computing the inverse
g
−
1
is much faster than multiplication in the group. Show ho
w t
o solve the DLP in an
interval of length
w
using a BSGS algorithm in approximately
√
w
group operations in the
average case.
g
a
for some
Exercise 13.3.8
Suppose one is given
g,h
∈
G
and
w,b,m
∈ N
such that
h
=
integer
a
satisfying 0
b
(mod
m
). Show how to reduce this problem to
the problem of solving a DLP in an interval of length
w/m
.
≤
a<w
and
a
≡
Exercise 13.3.9
Let
g
∈
G
have order
N
=
mr
where
r
is prime and
m
is log(
N
)-smooth.
=
g
x
and
w
are given such that 0
≤
Suppose
h
x<w
. Show how one can comput
e
x
by
combining the Pohlig-Hellman method and the BSGS algorithm in
O
(log(
N
)
2
+
√
w/m
)
group operations.
Exercise 13.3.10
Suppose one is given
g,h
∈
G
and
b
1
,b
2
,w
∈ Z
(
w>
0) such that
g
a
for some integer
a
satisfying either
b
1
≤
b
1
+
w<b
2
and
h
=
a<b
1
+
w
or
b
2
≤
a<b
2
+
w
. Give an efficient BSGS algorithm for this problem.
