Puzzle: Love in the land of kleptomaniacs

May 9, 2017 1:48 pm Last Updated: May 9, 2017 1:48 pm

Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a 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. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria’s hands?

This puzzle (titled “Love in Kleptopia”) was written by cryptographer Caroline Calderbank, the young daughter of mathematicians Ingrid Daubechies and Rob Calderbank.

It makes use of the Diffie–Hellman key exchange, one of the early major breakthrough methods of securely exchanging cryptographic keys over a public channel.

Mathematically, the Diffie-Hellman looks difficult. But Calderback’s answer is ingenious, and sums it up simply:

“Jan sends Maria a box with the ring in it and one of his padlocks on it. Upon receipt Maria affixes her own padlock to box and mails it back with both padlocks on it. When Jan gets it he removes his padlock and sends the box back to Maria. The ring, a symbol of their love, is delivered successfully!”