Cryptography Reference
In-Depth Information
5.4.3
Merkle Puzzles
In 1978, Ralph Merkle published a paper (Ref. [129]) which explains how to perform
confidential communication when the two parties do not share any secret, which is
the basic problem of public-key cryptography.
4
Here, we assume that the two parties
communicate over a channel which already provides authenticity and that they want to
agree on a common secret key.
We use the notion of
puzzle
: a puzzle is defined by (
y
,
c
) and consists of recov-
ering a key
r
such that
C
−
1
r
c
) where
C
is an encryption function.
We assume that doing an exhaustive search takes a complexity of
(
y
) is a triplet (
n
,
k
,
(
N
)foragiven
parameter
N
. We also use a one-way function
g
, which is used as a pseudorandom
generator.
We assume that
N
,
C
, and
g
are defined. The Merkle key establishment protocol
works as follows between
A
and
B
.
1.
A
takes a random
c
,
s
1
,
s
2
.
A
takes
N
random
r
i
.
A
computes
n
i
=
g
(
s
1
,
i
),
c
).
A
sends
c
and all
y
i
to
B
.
2.
B
picks a random
i
and solves the
i
-th puzzle. He recovers
n
i
and
k
i
.
B
sends
n
i
to
A
.
3.
A
gets
k
i
=
k
i
=
g
(
s
2
,
n
i
),
y
i
=
C
r
i
(
n
i
,
k
i
,
g
(
s
2
,
n
i
).
A
and
B
now share the
k
i
secret key.
(See Fig. 5.6.) The time complexity for
A
and
B
is
O
(
N
). If an adversary wants to
recover
k
i
without knowing
i
, she must solve all puzzles until
n
i
is correct, which takes
(
N
2
).
5.5
Authentication Chains
We put here some applications of conventional cryptography which are a little more
exotic. They illustrate how hash functions can be chained.
5.5.1
Merkle Tree
Before public-key cryptography was invented, researchers tried to invent the notion
of
digital signature scheme
.
5
A digital signature is an appendix to a digital document
which authenticates the signer. The signature is computed by using a private key, and it
is verified by using a public key. If a digital signature is “valid,” it proves that it has been
computed by someone who knew a given private key. This means that it is impossible
for an adversary to forge a valid signature without knowing the private key.
4
See Chapter 9.
5
The notion of digital signature and public key will be explained in Chapter 9.
Search WWH ::
Custom Search