Merkle’s Puzzles

 

A precursor to public key key exchange.

 

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

 

  1. INDEX – a random number
  2. PUZZLE – a puzzle that takes some time to solve and the solution is a number
  3. SOLN – the solution to the puzzle
  4. ESOLN(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 ESOLN(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)