Let’s do something different today. Let’s learn about cryptography by trying to solve a puzzle.

The Puzzle

You and I need to communicate via the National Postal Service. What you want to communicate is secret, so you don’t want a postal worker or some random schmoe who finds your mail in the mailbox or a package on your stoop to be able to open it up and read what’s inside, and you know from experience that any time you send something in the mail without securing it, it either gets read or (if it’s not just text) stolen. We must live in a country with a really corrupt postal service, I guess — kind of like the Internet.

We each have access to an arbitrary number of indestructible boxes, and an arbitrary number of indestructable key locks. Each box can have as many locks on it as you like. Unfortunately, each lock has only one key, and only the person who possesses the lock has the key. We can send things to each other in locked boxes, but of course the recipient doesn’t have the key to the lock because the sender has it. Sending the key unsecured will get it stolen or, worse, copied. We also have no way to meet each other in person to exchange keys securely (and if we did, we could just skip the postal service altogether, anyway).

How can we arrange, with these resources, to communicate securely with each other?

The Point

The point of this puzzle is to demonstrate a principle of cryptography known, among other terms, by the name “secure key exchange”. This particular puzzle is especially relevant to Diffie-Hellman key exchange. If you can figure this one out, you either have run across something like the problem in this puzzle before or probably have a mind suited to developing secure cryptographic algorithms.

Can you figure out the solution?