Merkle’s puzzles: the first public-key exchange (1974-1978)

As a student, Ralph Merkle asked whether two strangers could agree on a key over a public channel. His answer used only a symmetric cipher. Alice publishes many puzzles, each a session key locked by a deliberately weak key. Bob solves one at random and announces only its label. An eavesdropper does not know which puzzle Bob picked, and must open about half of them.

What to look for

Bob’s work stays flat while the eavesdropper’s grows with the number of puzzles. With N puzzles of N-trial difficulty, honest parties do O(N) work and the attacker O(N**2): a real but only quadratic advantage. Diffie and Hellman’s exponential gap came next.

The history behind this experiment: Breakthroughs in Cryptography.

One exchange

from random import Random

import matplotlib.pyplot as plt

import blockchainkit as bk

bits = 8
puzzles, alice_table = bk.crypto.merkle_puzzles(64, bits, randbits=Random(78).getrandbits)
bob = bk.crypto.solve_puzzle(puzzles[Random(1).randrange(64)], bits)
print("Bob announces", bob.puzzle_id.hex(), "after", bob.trials, "trials")
assert alice_table[bob.puzzle_id] == bob.key  # Alice looks the key up: shared secret.

Bob announces 05c37466005cee6c after 105 trials

What the eavesdropper must do

eve_trials = 0
for puzzle in puzzles:
    opened = bk.crypto.solve_puzzle(puzzle, bits)
    eve_trials += opened.trials
    if opened.puzzle_id == bob.puzzle_id:
        assert opened.key == bob.key
        break
print("Eve needed", eve_trials, "trials")

Eve needed 2050 trials

Honest work versus attack work

counts = [2**k for k in range(2, 9)]
bob_work, eve_work = [], []
for count in counts:
    puzzles, _ = bk.crypto.merkle_puzzles(count, bits, randbits=Random(count).getrandbits)
    trials = [bk.crypto.solve_puzzle(p, bits).trials for p in puzzles]
    bob_work.append(sum(trials) / count)  # One puzzle, on average.
    eve_work.append(sum(trials) / 2)  # Half the puzzles, on average.
fig, ax = plt.subplots(figsize=(7, 4))
ax.loglog(counts, bob_work, "o-", label="Bob: one puzzle")
ax.loglog(counts, eve_work, "s-", label="Eve: half of the puzzles")
ax.set(xlabel="number of puzzles", ylabel="trials", title="A quadratic gap from symmetric crypto")
ax.legend()
fig.tight_layout()

Exercise

Set the number of puzzles to 2**bits. Express Alice’s, Bob’s and Eve’s work in terms of N = 2**bits. If honest parties can afford 2**30 operations, how much work does the attacker face? Compare with Diffie-Hellman.