Secure Communication over Insecure Channels – Merkle’s Puzzles

Let’s say that Alice(X) and Bob(Y) want to share some secrets between them. They are looking for a secure way to do this. It is obvious that there exists Eve(Z), who is going to eavesdrop on their conversation,  but they wish to establish a secure communication in spite of that. The normal and key channels are completely exposed to Z, which implies that she will come to know of the secure key at some point of time.

X and Y decide to relax their restriction a bit. They say that Z should put polynomially more effort than X and Y to figure out their secure key.

Is it possible ? 

Merkle proved that it is and “Merkle’s Puzzles” was born.

How?

X and Y agree upon a number N beforehand. Y generates N puzzles* and assigns an unique identifier to each of them randomly.  Y sends these puzzles to X. X chooses one of the puzzles randomly and solves it. X sends back the unique identifier of the puzzle she solved to Y. Y knows which puzzle X has solved with the help of the unique identifier. X and Y have in fact established a secure communication.

What will Z do now ?

Z has access to two things – N puzzles and the identifier. She can’t do anything with the identifier as she doesn’t know which puzzle is assigned to which identifier. Hence, she decides to solve all the puzzles. If each puzzle takes O(N) time (equally hard to solve), then the total time taken by Z is O(N * N) [as there are N puzzles]. Hence, Z’s effort is quadratic compared to X and Y’s linear efforts.

Why is it of interest ? 

Merkle came up with this idea when he was an undergraduate student in 1974. This technique shows signs of public-key cryptosystem even before it became a terminology. Very recently, [1] showed that any random key exchange protocol in which the honest users make n queries to the random oracle, can be broken by an adversary. making O(n^2) queries to the oracle. I am planning to drill into [1] in the next post.

*puzzle – In this context, puzzle is a cryptogram which is designed to be broken.

[1]”Merkle Puzzles are Optimal — an O(n^2)-query attack on key exchange from a random oracle”(http://www.boazbarak.org/Papers/merkle.pdf)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s