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):


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.
Alice picks one at random and brute force it. She should be able to recover x and y.
Alice encrypts her message to Bob by using y she just recovered (using symmetric cipher). Her message will contain x, the puzzle number.
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).