Cryptography Reference
In-Depth Information
1
p
(
k
)
u
←
u
←
Z
p
]
Pr[
A
(
p, g, y
)=Log
p,g
(
y
):(
p, g
)
I
k
;
y
≤
for all
k
≥
k
0
.
In this terminology, the PPT algorithm
A
models an adversary who tries to
compute the discrete logarithm of
y
to the base
g
, or, equivalently, to invert the
discrete exponentiation function Exp
p,g
. Furthermore, the term
u
←
Z
p
y
∈
Z
p
occur with the same
suggests that
y
is uniformly distributed, meaning that all
y
|
Z
p
|
probability (i.e., Pr[
y
]=1
/
=1
/
(
p
−
1)). This is just another way of saying
∈
R
Z
p
. Similarly, the term
that
y
u
←
(
p, g
)
I
k
suggests that the pair (
p, g
) is uniformly distributed, meaning that all (
p, g
)
∈
I
k
occur with the same probability. Consequently, the probability statement of
Definition 7.4 can be read as follows: if we randomly select both the index
i
=
(
p, g
)
I
k
with security parameter
k
and
y
=
g
x
, then the probability that the PPT
algorithm
A
successfully computes and outputs Log
p,g
(
y
) is negligible (i.e., smaller
than any polynomial bound). This means that Exp
p,g
∈
cannot be inverted by
A
for all
but a negligible fraction of input values.
Even if the security parameter
k
is very large, there may be pairs (
p, g
) such
that
A
can correctly compute Log
p,g
(
y
) with a probability that is nonnegligible. For
example, if
p
1 has only small prime factors, then there is an efficient algorithm
due to Steve Pohlig and Martin E. Hellman that can be used to compute the discrete
logarithm function [1]. In either case, the number of such special pairs (
p, g
) is
negligibly small as compared to all keys with security parameter
k
.If(
p, g
) is
randomly (and uniformly) chosen from
I
k
, then the probability of obtaining such
a pair (i.e., a pair for which
A
can compute discrete logarithms) is negligibly small.
Under the DLA, the Exp family represents a family of one-way functions.
It is used in many public key cryptosystems, including, for example, the ElGamal
public key cryptosystem (see Sections 14.2.3 and 15.2.2) and the Diffie-Hellman key
exchange protocol (see Section 16.3). Furthermore, several problems are centered
around the DLA and the conjectured one-way property of the discrete exponential
−