Cryptography Reference
In-Depth Information
as we know it today [4].
1
The idea is simple and has become known as
Merkle's
Puzzles
.
Protocol 16.1
Merkle's Puzzles.
A
B
(
n
)
(
n
)
Generate
P
i
=(
i, K
i
) for
i
=1
,...,n
Permute
P
1
,...,P
n
P
π
(1)
,...,P
π
(
n
)
−→
Randomly select
P
i
Solve
P
i
i
←−
(
K
i
)
(
K
i
)
Let A and B be two entities that can communicate with each other over a public
but authentic channel. A and B can then use Protocol 16.1 to establish a shared secret
key
K
. The protocol takes a security parameter
n
on either side and then proceeds
with the following three steps:
•
First, A generates
n
puzzles
P
1
,...,P
n
, randomly permutes the puzzles
(using permutation
π
), and sends
P
π
(1)
,...,P
π
(
n
)
to B. Each puzzle
P
i
consists of an index
i
and a randomly chosen secret key
K
i
(i.e.,
P
i
=
(
i, K
i
)). Solving a puzzle is technically feasible but requires a nonnegligible
computational effort (as explained later).
•
Second, B randomly selects a puzzle
P
i
from
P
π
(1)
,...,P
π
(
n
)
and solves it.
The solution is (
i, K
i
), and B sends back to A the index
i
(the transmission is
in the clear).
•
Third, A can use
i
to extract the secret key
K
i
, and this key can then be used
as a shared secret key between A and B.
Having a closer look at the protocol, one realizes that B gets
K
i
after having
solved one single puzzle (i.e.,
P
i
), whereas an adversary gets
K
i
only after having
solved all
n
puzzles and having found the puzzle with the appropriate index
i
(on
the average, the adversary has to solve half of the puzzles). For sufficiently large
n
, this is computationally infeasible for the adversary, and hence Merkle's Puzzles
provide a theoretically interesting possibility to have two entities establish a secret
key between them.
1
Note that this article appeared in the
Communications of the ACM
in 1978 (i.e., three years after it
was submitted to the magazine).
