Cryptography Reference
In-Depth Information
Algorithm 13
Baby-step-giant-step (BSGS) algorithm
INPUT:
g,h
G
of order
r
OUTPUT:
a
su
ch that
h
∈
g
a
,or
=
⊥
=
√
r
1:
m
2:
Initialise an easily searched structure (such as a binary tree or a hash table)
L
3:
x
=
1
4:
for
i
=
0to
m
do
Compute baby steps
store (
x,i
)in
L
, easily searchable on the first coordinate
5:
=
x
xg
6:
7:
end for
8:
u
g
−
m
=
0
10:
while
(
y,
)
9:
y
=
h
,
j
=
∈
L
do
Compute giant steps
y
=
yu
,
j
=
j
+
1
11:
12:
end while
13:
if
∃
(
x,i
)
∈
L
such that
x
=
y
then
return
i
+
mj
14:
15:
else
16:
return
⊥
17:
end if
Note that the BSGS algorithm is deterministic. The algorithm also solves the decision
problem (is
h
?) though, as discussed in Section
11.6
, there are usually faster solutions
to the decision problem.
∈
g
Theorem 13.3.1
Let G be a group of order r. Suppose that elements of G are represented
using O
(log(
r
))
bits and that the group operations can be performed in O
(
log(
r
)
2
)
bit
operations. The BSGS algorithm for th
e
DLP in G has running time O
(
√
r
log(
r
)
2
)
bit
operations. The algorithm requires O
(
√
r
log(
r
))
bits of storage.
Proof
The algorithm computes
√
r
group operations for the baby steps. The cost of
inserting each group element into the easily searched structure is
O
(log(
r
)
2
) bit opera-
tions, since comparisons require
O
(log(
r
)) bit operations (this is where th
e
assumption on
the size of element representations appears). The structure requires
O
(
√
r
log(
r
)) bits of
storage.
The computation of
u
g
−
m
in line 8 requires
O
(log(
r
)) group operations.
The algorithm needs one group operation to compute each giant step. Searching the
structure takes
O
(log(
r
)
2
) bit operations. In t
h
e worst case, one has to compute
m
giant
steps. The total running time is therefore
O
(
√
r
log(
r
)
2
) bit operations.
=
The storage requirement of the BSGS algori
th
m quickly becomes prohibitive. For exam-
ple, one can work with primes
r
such that
√
r
is more than the number of fundamental
particles in the universe!
