Cryptography Reference
In-Depth Information
20
The Diffie-Hellman problem and
cryptographic applications
This chapter introduces some basic applications of the discrete logarithm problem in
cryptography, such as Diffie-Hellman key exchange and “textbook” Elgamal encryption.
A brief security analysis of these systems is given. This motivates the computational and
decisional Diffie-Hellman problems (CDH and DDH). A thorough discussion of these
computational problems will be given in Chapter
21
.
20.1 The discrete logarithm assumption
The discrete logarithm problem (DLP) was defined in Definition
13.0.1
. Our main interest
is the DLP in an algebraic group or algebraic group quotient over a finite field
F
q
(for
example, elliptic curves, the multiplicative group of a finite fields, tori etc.). We always use
multiplicative notation for groups in this chapter. As discussed in Section
13.2
, in practice
we usually restrict to groups of prime order
r
.
Recall that the difficulty of the DLP is defined with respect to an instance generator
that runs on input a security parameter
κ
. An algorithm to solve the DLP with respect to
a given instance generator is only required to succeed with a noticeable probability. The
discrete logarithm assumption
is that there exist instance generators that, on input
κ
,
output instances of the DLP such that no algorithm
A
running in polynomial-time in
κ
can solve the DLP apart from with negligible (in
κ
) probability. The cryptosystems in this
chapter rely on the discrete logarithm assumption (and other assumptions).
20.2 Key exchange
20.2.1 Diffie-Hellman key exchange
The starting point of discrete logarithms (indeed, of public key cryptography) is the seminal
paper of Diffie and Hellman [
166
] from 1976 (more recently it became known that this idea
was also found by Williamson at GCHQ in 1974).
Suppose Alice and Bob want to agree on a random key
K
. Assume they both know
an algebraic group or algebraic group quotient
G
and some element
g
∈
G
of prime
