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.
 
Search WWH ::




Custom Search