**Merkle’s Puzzles**

A precursor to public key key exchange.

Alice creates a table consisting of a million entries. Each entry consists of:

- INDEX – a random number
- PUZZLE – a puzzle that takes some time to solve and the solution is a number
- SOLN – the solution to the puzzle
- E
_{SOLN}(INDEX) – the index, encrypted with the solution of the puzzle

Alice sends to Bob only the INDEX and PUZZLE fields of the table.

Bob picks a puzzle at random and solves it. Then Bob
computes E_{SOLN}(INDEX), as he knows both the INDEX and SOLN values
and sends the result to Alice.

Alice looks up the table to find the puzzle this value corresponds to… and…..

Alive and Bob communicate happily using SOLN as the private key, while Eve is way too busy working out a million puzzles.

**Note on complexity**

**Suppose we assume the puzzle takes 1
million operations to solve. Suppose we assume that a computer can perform a
million operations per second.**

**Then Bob takes 1 sec to solve the puzzle.
However Eve takes 1 million seconds, which means she needs 11 days to recover
the key.**

**If we make the puzzle and the number of
puzzles larger by 10 (10 million operations, 10 million puzzles) then Bob needs
10 seconds, but Eve need 1100 days (3 years)**