Cryptography Reference
In-Depth Information
13
Basic discrete logarithm algorithms
This chapter is about algorithms to solve the discrete logarithm problem (DLP) and some
variants of it. We focus mainly on deterministic methods that work in any group; later
chapters will present the Pollard rho and kangaroo methods, and index calculus algorithms.
In this chapter, we also present the concept of generic algorithms and prove lower bounds
on the running time of a generic algorithm for the DLP. The starting point is the following
definition (already given as Definition
2.1.1
).
Definition 13.0.1
Let
G
be a group written in multiplicative notation. The
discrete loga-
rithm problem
(
DLP
)is:given
g,h
g
a
. We sometimes
∈
G
find
a
, if it exists, such that
h
=
denote
a
by log
g
(
h
).
As discussed after Definition
2.1.1
, we intentionally do not specify a distribution on
g
or
h
or
a
above, although it is common to assume that
g
is sampled uniformly at random in
G
, and
a
is sampled uniformly from
{
}
.
Typically,
G
will be an algebraic group over a finite field
1
,...,
#
G
F
q
and the order of
g
will be
known. If one is considering cryptography in an algebraic group quotient then we assume
that the DLP has been lifted to the covering group
G
. A solution to the DLP exists if and
only if
h
(i.e.,
h
lies in the subgroup generated by
g
). We have discussed methods to
test this in Section
11.6
.
∈
g
Exercise 13.0.2
Consider the discrete logarithm problem in the group of integers modulo
p
under
addition
. Show that the discrete logarithm problem in this case can be solved in
polynomial-time.
Exercise
13.0.2
shows there are groups for which the DLP is easy. The focus in this
topic is on algebraic groups for which the DLP seems to be hard.
Exercise 13.0.3
Let
N
be composite. Define the discrete logarithm problem DLP-MOD-N
in the multiplicative group of integers modulo
N
. Show that FACTOR
≤
R
DLP-MOD-N.
Exercise
13.0.3
gives some evidence that cryptosystems based on the DLP should be at
least as secure as cryptosystems based on factoring.
