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
Search WWH ::




Custom Search