# Why does Merkle's Puzzle requires Eve quadratic complexity of effort to break the system?

The way Applied cryptography 2ED explains the puzzle is as follows (I paraphrase it):

1. Bob generates 2^20 messages of the form x,y where x is a puzzle number and y is the secret key. Both x and y are different for each of the one million message. Encrypt each message using symmetric cipher with a different 20-bit key. Send all messages to Alice.

2. Alice picks one at random and brute force it. She should be able to recover x and y.

3. Alice encrypts her message to Bob by using y she just recovered (using symmetric cipher). Her message will contain x, the puzzle number.

4. Bob looks up the secret key for puzzle x and decrypts the message.

According to the book and many Internet sources, Eve would have to do theta(n^2) work to brute force the communication.

The book doesn't seem to say much about how x is included in Alice's response to Bob. It must be not be encrypted right? Because Bob has to do a O(1) look up. That is, Alice would have to send x+E(private message, y) to Bob.

Then why can't Eve just wait for Alice's response to Bob and compute that puzzle?

This is the brute force algorithm I think would satisfy 2^n if x is encrypted in Alice's response as well.

for y in 2^20:
for x in 2^20:
c = symmetric_enc(y, x)
if c == c_from_alice:
return yes, c, x, y
return no, none, none, none


But if x is encrypted in Alice response, then Bob have to brute force like Eve too, no?

$x$ is not encrypted in Alice’s response. The point is that, even though Eve knows the puzzle number $x$, she has no way to tell which of the puzzles Bob sent is the one with this number, unless she solves all of them (or at any rate half of them, on average).
• Thanks. If x is encrypted in Alice's response, how is Bob able to tell which x in constant time? Now that I think about it, Bob might only need to do n encryption to find out which x. In other words, since Bob has a table with x and key as columns, he can do 2^20 encryptions to find out. So this is the difference and my assumption that Bob does only O(1) is wrong right? Otherwise, Eve can do O(1) as well. Am I correct? Does x really have to be encrypted in Alice's response? – CppLearner Oct 28 '13 at 10:57
• @CppLearner Sorry, I should have been clearer: $x$ is not encrypted in Alice’s response. I have edited the answer to make it clearer, I hope. – Robin Houston Oct 28 '13 at 11:55