Cryptography Reference
In-Depth Information
distribution channels for public keys in order to prevent an adversary from replacing
the public key of a user.
Besides the concept of public-key encryption, Diffie and Hellman also introduced
two other public-key primitives. One of them is
digital signatures
, which are the
public-key analogues of MACs but, as we already mentioned, have important advan-
tages and make it possible, for example, to electronically sign contracts. The other
primitive is
key agreement
through public channels, which was also discovered inde-
pendently by RalphMerkle and is a protocol that enables two parties who do not share
any information to generate a shared secret key by communicating over an insecure
authenticated channel. This was a powerful idea as nothing even remotely similar
was publicly known at the time and it was the only one of these three primitives for
which Diffie and Hellman offered a concrete construction called the
Diffie-Hellman
key agreement protocol
, which we study in the next section.
A
key agreement protocol
between two parties, say, Alice and Bob, proceeds
by Alice and Bob taking turns in sending messages to each other and terminates
with both parties obtaining a common value
k
which will be their shared secret key.
Abstractly,
Π
may be modeled as a pair of probabilistic machines
A
,
B
that, starting
with a security parameter 1
n
run the protocol as indicated. The
protocol transcript t
Π
is the sequence of messages exchanged by
A
and
B
which, since they implement PPT
algorithms, will be different each time the protocol is run. The object of the protocol
is to prevent an adversary
Π
that sees the transcript from learning information about
the secret key
k
. Thus the security of a key agreement protocol
A
Π
may be defined
through the following experiment:
Definition 7.1
The
key agreement experiment
KA
eav
A,Π
(
n
)
, where
Π
is a key agree-
ment protocol,
A
a PPT adversary, and
n
any value of the security parameter, is the
following:
1. The parties
A
,
B
, execute the protocol on input 1
n
and they output a key
k
.
2. A random bit
b
is chosen. A key
k
is defined by setting
k
←{
0
,
1
}
:=
k
if
0 and choosing it at random,
k
←{
n
,if
b
b
=
0
,
1
}
=
1.
and
k
and outputs a bit
b
.
4. The output of the experiment is defined to be 1 if
b
3.
A
is given
t
Π
=
b
and 0 otherwise. If
KA
eav
A
,Π
(
n
)
=
1 then we say that
A
succeeded
.
Definition 7.2
The key agreement protocol
Π
is said to be
secure in the presence
of an eavesdropper
if, for every PPT adversary
A
, there exists a negligible function
KA
eav
negl
such that Pr
(
A,Π
(
n
)
=
1
)
≤
1
/
2
+
negl
(
n
)
. The advantage of
A
in the
KA
eav
experiment is defined as
|
Pr
(
A,Π
(
n
)
=
1
)
−
1
/
2
|
.
The definition says that an adversary eavesdropping the key agreement protocol
cannot distinguish the key
k
from a randomly generated key. This is not a very strong
security concept because it does not provide assurance of the identities of the parties,
so that a protocol which is secure in this sense may be vulnerable, as we shall soon
see, to certain active attacks.