Cryptography Reference
In-Depth Information
order
r
(everyone in the world could use the same
g
). They perform the following
protocol:
g
a
to Bob.
Alice chooses a random integer 0
<a<r
and sends
c
1
=
g
b
to Alice.
Bob chooses a random integer 0
<b<r
and sends
c
2
=
c
2
.
On receiving
c
2
Alice computes
K
=
c
1
.
Hence, both players share the key
K
On receiving
c
1
Bob computes
K
=
g
ab
. One can derive (see Definition
20.2.10
below) a bitstring from the group element
K
for use as the key of a symmetric encryption
scheme. Hence, encryption of data or other functionalities can be implemented using
traditional symmetric cryptography. The key
K
is called the
session key
and the values
c
1
,
c
2
in the protocol are called
messages
or
ephemeral keys
.
We discuss the security of key exchange protocols (in particular, person-in-the-middle
attacks and authenticated key exchange) in Section
20.5
. For the remainder of this section
we consider the simplest possible attacker. A
passive attacker
or
eavesdropper
(i.e., an
attacker who learns
g,
c
1
and
c
2
, but does not actively interfere with the protocol) cannot
determine
K
unless they can solve the following computational problem.
=
Definition 20.2.1
The
Computational Diffie-Hellman problem (CDH)
1
is: given the
triple (
g,g
a
,g
b
) of elements of
G
to compute
g
ab
.
An extensive discussion of the computational Diffie-Hellman problem will be given in
Chapter
21
.
F
11
?
Exercise 20.2.2
What is the solution to the CDH instance (2
,
4
,
7) in the group
Suppose one is an eavesdropper on a Diffie-Hellman session and tries to guess the
session key
K
shared by Alice and Bob. The following computational problem is precisely
the problem of determining whether the guess for
K
is correct. This problem arises again
later in the chapter in the context of Elgamal encryption.
Definition 20.2.3
Let
G
be a group and
g
G
.The
Decisional Diffie-Hellman problem
(DDH)
is, given a quadruple (
g,g
a
,g
b
,g
c
) of elements in
∈
g
to determine whether or not
g
c
g
ab
.
=
Saying that a computational problem such as DDH is hard is slightly less straightforward
than with problems like DLP or CDH, since if (
g,g
a
,g
b
,g
c
) are chosen uniformly at random
in
G
4
then the solution to the DDH problem is “no” with overwhelming probability. Clearly,
an algorithm that says “no” all the time is not solving the DDH problem, so our notion of
success must capture this. The correct approach is to define a DDH solver to be an algorithm
that can distinguish two distributions on
G
4
, namely the distribution of
Diffie-Hellman
1
This assumption comes in two flavours, depending on whether
g
is fixed or variable. We discuss this issue in more detail later.
But, as is the convention in this topic, whenever we write “Given
...
compute
...
” one should understand that all of the inputs
are considered as variables.
