The trouble with these puzzles is that it is insanely hard to state them correctly so as to capture the desired underlying formal problem, but exclude unwanted real-world hacks. It is probable that the puzzle is meant to elicit something like Diffie-Helman exchange, as Adam intuited. But the puzzle as stated by Henry does not preclude, for example, just sending the key in advance. The corrupt postal workers will hang on to any locked box if they think a key is coming later, but we are not told that they will hang on to a key if they think a box is coming later. On Mon, May 9, 2016 at 12:14 PM, James Propp <jamespropp@gmail.com> wrote:
Maybe I'm not entering into the proper spirit, but I imagine I would send her an innocent-seeming sketch of a cityscape, asking her to treasure it. Then weeks later I would send the locked box, with a letter saying "You already have the key." The profile of the cityscape would provide the shape of the key that she would have to manufacture in order to open the box.
Or something like that.
Jim Propp
On Mon, May 9, 2016 at 10:45 AM, Mike Speciner <ms@alum.mit.edu> wrote:
Man-in-the-middle attack. --ms
On 09-May-16 10:38, Adam P. Goucher wrote:
Diffie-Hellman key exchange.
Best wishes,
Adam P. Goucher
Sent: Monday, May 09, 2016 at 2:49 PM
From: "Henry Baker" <hbaker1@pipeline.com> To: math-fun@mailman.xmission.com Subject: [math-fun] Russian Postal Problem
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun