# Would it be possible to negotiate a key of 128 or 256 bits strength using Merkle puzzles?

One can be fascinated by the simplicity of the schemes created by Ralf Merkle; like the Merkle tree or his key negociation protocol over an insecure channel.

Wikipedia has some material on "Merkle puzzles" (wikipedia_page) and his seminal paper can be found online (article_pdf).

But, could this venerable construction be put to use in order to reach nowadays security strength requirements (i.e. a key of at least 128 bits strength, or even 256 bits for the real paranoids out there).

Thanks!

The complexity required for the attacker to break the scheme is at maximum quadratic in the security parameter $n$. It is not enough for a secure cryptographic protocol where you want exponential complexity to break the scheme.
Say $n$ is the difficulty of solving the puzzles and $m$ is the number of puzzles. Alice needs to solve one puzzle in time $O(n)$ but Bob will need to look in his puzzles to find the correct key. He needs roughly $O(m)$ time. The scheme has then $O(n+m)$ time complexity.
For breaking the scheme, Eve can brute force all the puzzles, she then needs $O(nm)$ time complexity. If you want to have this complexity be around $2^{128}$ you need to send an incredible amount of puzzles and/or puzzles too hard.