The sixteenth Theory Weekly Meeting will happen this Friday between 4:00 – 5:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :
4:00 – 4:50 pm – The continuation of the talk series by Marco Gaboardi. This will be the final installment and will center around Differential Privacy like his earlier talks.
4:50 – 5:00 pm – Socializing with the Theory community.
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.
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,  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  in the next post.
*puzzle – In this context, puzzle is a cryptogram which is designed to be broken.
”Merkle Puzzles are Optimal — an O(n^2)-query attack on key exchange from a random oracle”(http://www.boazbarak.org/Papers/merkle.pdf)