Cryptography Reference
In-Depth Information
Example 3.2
This example is studied in detail in Chap.
6
since it has important
cryptographic applications. Let
I
Z
p
=
={
(
,
)
|
}
and consider a PPT
parameter generation algorithm that, on input 1
n
, outputs an element
p
g
p
prime,
g
(
p
,
g
)
∈
I
,
where len
n
(we already know that, given
p
, a PPT algorithm outputting a
primitive root modulo
p
exists and we will also see in Chap.
6
that there exists a
PPT algorithm which, on input 1
n
, outputs an
n
-bit prime
p
). Consider also a PPT
sampling algorithm that, given
(
p
)
=
(
p
,
g
)
∈
I
, outputs a random element of
Z
p
−
1
or,
equivalently, a random integer in
{
0
,
1
,...,
p
−
2
}
. We may then define, for each
(
p
,
g
)
∈
I
, the function
dexp
(
p
,
g
)
: Z
p
−
1
→ Z
p
g
x
mod
p
. This is a family of functions indexed by
I
which are actually
bijections because
g
is a generator of
given by
x
→
Z
p
and so
Z
p
g
0
g
2
g
p
−
2
={
,
g
,
,...,
}
(in
fact, they are group isomorphisms since
g
x
+
x
g
x
g
x
). Moreover, these functions
are easy to compute by means of the binary exponentiation algorithm. The inverse
of
dexp
(
p
,
g
)
=
is the
discrete logarithm
function
dlog
(
p
,
g
)
: Z
p
→ Z
p
−
1
,given
∈ Z
p
. Computing the discrete logarithm
is presumed to be hard relative to the parameter generation algorithm and so a PPT
algorithm should only be able, given
x
where
g
x
by
dlog
(
p
,
g
)
(
y
)
=
=
y
and
g
x
mod
p
, to guess
x
with negligible
probability. Thus this family is thought to be one-way.
(
,
)
p
g
A discrete logarithm function can be defined, more generally, by considering
instead of
Z
p
, any cyclic group
G
of order
q
and a generator
g
∈
G
. Then we have
a group isomorphism
dexp
(
G
,
g
)
: Z
q
→
G
g
x
. The inverse isomorphism, given by
dlog
(
G
,
g
)
(
given by
x
→
y
)
=
x
where
g
x
=
y
∈
G
is the discrete logarithm function corresponding to the pair
(
G
,
g
)
(
x
is
then called the discrete logarithm of
y
with respect to
g
,
x
log
g
y
). The following
example shows that computing discrete logarithms is not always difficult:
=
Example 3.3
Consider the family of additive cyclic groups
Z
p
and a parameter
generation PPT algorithm that, on input 1
n
, outputs a pair
(
p
,
g
)
, where
p
is a prime
with len
(
p
)
=
n
and
g
a nonzero element of
Z
p
, which is also a generator of
Z
p
. Then
we have as before the functions
dmul
(
p
,
g
)
: Z
p
→ Z
p
, given by
x
→
gx
mod
p
(these are really the “discrete exponential” functions corresponding to these groups
except that, as the groups are additive now, exponentiation becomes multiplication).
These functions are isomorphisms, and their inverses are the additive analogue of the
discrete logarithm functions, namely, the functions
Z
p
→ Z
p
that to each
y
∈ Z
p
assign the unique
x
∈ Z
p
such that
gx
mod
p
=
y
. But finding such an
x
from
∈ Z
p
,
g
has a multiplicative inverse modulo
p
which can be obtained by using the extended Euclidean algorithm. Then we recover
x
by computing
x
(
p
,
g
)
and
y
is easy because, as
g
g
−
1
mod
p
=
(
·
y
)
mod
p
. Hence computing discrete logarithms
in the additive groups
is far from
one-way. Note that, in order to compute discrete logarithms in this way, we use
Z
p
is easy and the family of functions
dmul
(
p
,
g
)
