One-Way Functions - Contemporary Cryptography - page 174

log g x . This value refers to the element of Z p− 1 to which g must be set to the power

of in order to get x .
Exp p,g is efficiently computable, for example, by using the square-and-
multiply algorithm (i.e., Algorithm 3.3). Contrary to that (and contrary to the log-
arithm function in the real numbers), no efficient algorithm is known to exist for
computing discrete logarithms for sufficiently large prime numbers p . All known al-
gorithms have a super-polynomial running time, and it is widely believed that Log p,g
is not efficiently computable.
Earlier in this chapter we said that—in order to use complexity-theoretic
arguments—we must consider families of one-way functions. In the case of the
discrete exponentiation function, we may use p and g as indexes for an index set
I . In fact, I can be defined as follows:

Z p }

I := { ( p, g ) | p ∈ P ; g a generator of

Using this index set, we can formally define the Exp family (i.e., the family of
discrete exponentiation functions)

Z p− 1 −→ Z p ,x g x Exp := { Exp p,g : −→ } ( p,g ) ∈I

and the Log family (i.e., the family of discrete logarithm functions)

Z p −→ Z p− 1 ,x Log := { Log p,g : −→ log g x } ( p,g ) ∈I .

If we want to employ the Exp family as a family of one-way functions, then
we must make sure that it is hard to invert, meaning that it is not known how
to efficiently compute discrete logarithms. This is where the discrete logarithm
assumption (DLA) as formally expressed in Definition 7.4 comes into play.

Definition 7.4 (Discrete logarithm assumption) Let I k := { ( p, g ) ∈ I || p | = k }

, 3 p ( k ) be a positive polynomial, and A ( p, g, y ) be a PPT algorithm. Then
the DLA says that there exists a k 0 ∈ N

for k ∈ N

, such that

This means that the index set I consists of disjoint subsets I k (i.e., I =

I k ). Consequently,

3

k∈ N

k may be considered the security parameter of i =( p, g ) ∈ I k .