One-Way Functions - Contemporary Cryptography - page 176

function. The most important problems are the discrete logarithm problem (DLP)
captured in Definition 7.5, the (computational) Diffie-Hellman problem (DHP) cap-
tured in Definition 7.6, and the Diffie-Hellman decision problem (DHDP) captured
in Definition 7.7. The problems can be specified in arbitrary cyclic groups.

Definition 7.5 (Discrete logarithm problem) Let G be a cyclic group, g be a gen-
erator of G , and h be an arbitrary element in G . The DLP is to determine an integer
x such that g x = h .

Definition 7.6 (Diffie-Hellman problem) Let G be a cyclic group, g be a generator
in G , and x and y be two integers smaller than the order of G (i.e., x, y < | G | ). The

terms g x and g y then represent two elements in G . The DHP is to determine g xy

from g x and g y .

Definition 7.7 (Diffie-Hellman decision problem) Let G be a cyclic group, g be a
generator of G , and r , s , and t be three positive integers smaller than the order of G
(i.e., r, s, t < ). The terms g r , g s , g t , and g rs then represent elements in G .The

DHP is to determine whether g rs or g t

| G |

solves the DHP for g r and g s . Alternatively

g r ,g s ,g rs g r ,g s ,g t speaking, the DHDP is to distinguish the triples and when

they are given in random order.

When giving all of these problems, it may be interesting to know how they are
related. This is done by giving complexity-theoretic reductions from one problem to
another (see Definition 6.10 for the notion of a polynomial-time reduction). In fact,
in can be shown that DHP ≤ P DLP (i.e., the DHP polytime reduces to the DLP) and

that DDHP ≤ P DHP (i.e., the DDHP polytime reduces to the DHP) in an arbitrary

finite Abelian group. So the DLP is the hardest among the problems (i.e., if one is
able to solve the DLP, then one is trivially able to solve the DHP and the DDHP).
The exact relationship and the complexity of the corresponding proof (if it is known
in the first place) depend on the actual group in use. In many cyclic groups, the
DLP and the DHP have been shown to be computationally equivalent [2, 3]. There
are, however, groups in which one can solve the DDHP in polynomial time, but the
fastest known algorithm to solve the DHP requires subexponential time. In order to
better understand the DLP and the underlying DLA, it is worthwhile to have a look
at the currently available algorithms to compute discrete logarithms. This is done in
Section 7.4.

7.2.2 RSA Function

Let n be the product of two distinct primes p and q (i.e., n = pq ), and e be relatively
prime to φ ( n ). Then the function