Love in Kleptopia

Today, I am going to present a very nice logical puzzle that I chanced upon recently. The puzzle, popularly known as "Love in Kleptopia", is stated as follows:

Alice and Bob have fallen in love (via long, romantic chats on facebook) and Bob wishes to mail Alice an engagement ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Alice and Bob each have plenty of padlocks, but none to which the other has a key. Under these circumstances, how can Bob get the ring safely into Alice’s hands?


The solution, which is quite ingenious, follows:

Bob sends Alice a box with the ring in it and one of his padlocks on it. Upon receipt, Alice affixes her own padlock to the box and mails it back with both padlocks on it. When Bob receives it, he removes his own padlock and sends the box back to Alice. So now, Alice receives the box with the ring in it and a padlock on it to which she has the key. Voila!


The solution stated above is not only elegant, but also provides an idea that is fundamental in Diffie-Hellman key exchange, which was quite a historic breakthrough in cryptography!