Merkle's Puzzles

Merkle's puzzle is the name of the first key exchange protocol, in which the two parties do not already have to share a secret key with each other or a third party. It was discovered in 1974 by Ralph Merkle, but not published until 1978. The existence of such a protocol was considered impossible a long time, and his discovery can be seen as the beginning of the public-key cryptography.

Description

If Alice wants to exchange a key with Bob, she first puts a table of random keys to the desired length. For a given symmetric encryption method it now selects random key with a not too long length of bits and each of these keys is encrypted with a table entry, together with its index into the table. The cryptograms sending in random order to Bob.

Bob chooses a random ciphertext and tries all possible keys until he guesses correctly and can decrypt the ciphertext. But he needs more than attempts. He remembers the key and sends the index back to Alice, who thus knows what sort key Bob.

Security

An attacker eavesdropping the communication between the two, first sees the cryptograms that sends Alice to Bob, then the index that Bob sends back the, but is independent of the order in which the ciphers were sent. Thus, he has no choice but as long to crack encrypted files until it finds one that contains the index. For this he needs attempts at his life is so squarely in the world of Alice and Bob.

Suppose that Bob can to try each key per second. Then, during and for less than a second takes to crack a cipher, an attacker with the same computing power but on average half a year.

In theoretical cryptography is nowadays generally accepted that the term of the attacker is polynomial in a security parameter. By this definition, a quadratic difference in the duration between the users and the attacker is not enough, the attacker could try all ciphers. The process is in such a model that is not safe.