Cryptography Reference
In-Depth Information
Exercise 13.3.11
Let
g
G
where the order of
g
and
G
are not known. Suppose one is
given integers
b,w
such that the order of
g
lies in the interval [
b,b
∈
+
w
). Explain how to
use the BSGS method to compute the order of
g
.
Exercise 13.3.12
.
Show that one can solve the DLP of all
n
elements
h
i
to the base
g
i
n ap
proximately 2
√
nr
Suppose one is given an element
g
of order
r
and
h
1
,...,h
n
∈
g
group operations (optimised for the worst case) or approximately
√
2
nr
(optimised for the
average case).
Exercise 13.3.13
G
of order
r
, an integer
w
and an instance
generator for the discrete logarithm problem that outputs
h
Suppose one is given
g
∈
=
g
a
∈
≤
G
such that 0
a<w
{
−
}
according to some known distribution on
. Assume that the distribution
is symmetric with mean value
w/
2. Determine the optimal BSGS algorithm to solve such
a problem.
0
,
1
,...,w
1
g
a
where
a
has
a representation as a non-adjacent form NAF (see Section
11.1.1
) of length
n<
log
2
(
r
).
Give an efficient BSGS algorithm to find
a
. What is the running time?
Exercise 13.3.14
Suppose one is given
g,h
∈
G
and
n
∈ N
such that
h
=
13.4 Lower bound on complexity of generic algorithms for the DLP
This section presents a lower bound for the complexity of the discrete logarithm problem
in groups of prime order for algorithms that do not exploit the representation of the group;
such algorithms are called generic algorithms. The main challenge is to formally model
such algorithms. Babai and Szemeredi [
18
] defined a black box group to be a group with
elements represented (not necessarily uniquely) as binary strings and where multiplication,
inversion and testing whether an element is the identity are all performed using oracles.
Nechaev [
405
] used a diff
e
rent model (for which equality testing does not require an oracle
query) and obtained
(
√
r
) time and space complexity.
Nechaev's paper concerns deterministic algorithms, and so his result does not cover the
Pollard algorithms. Shoup [
494
] gave yet anothe
r
model for generic algorithms (his model
allows randomised algorithms) and proved
(
√
r
) time complexity for the DLP and some
related problems. This lower bound is often called the
birthday bound
on the DLP.
Shoup's formulation has proven to be very popular with other authors and so we present
it in detail. We also describe the model of generic algorithms by Maurer [
364
]. Further
results in this area and extensions of the generic algorithm model (such as working with
groups of composite order, working with groups endowed with pairings, providing access
to decision oracles etc.) have been given by Maurer and Wolf [
367
], Maurer [
364
], Boneh
and Boyen [
71
,
72
], Boyen [
90
], Rupp, Leander, Bangerter, Dent and Sadeghi [
456
].
13.4.1 Shoup's model for generic algorithms
Fix a constant
t
∈ R
>
0
. When
G
is the group of points on an elliptic curve of prime order
(and log means log
2
as usual), one can take
t
=
2.
