In the summer of 1958, Michael Rabin returned to IBM's Think Tank-on-the-Hudson, the Lamb Estate. John McCarthy was there struggling with list processing in FORTRAN and posed a puzzle to Rabin. Here is how Rabin remembers it.
There are two countries in a state of war. One country is sending spies into the other country. The spies do their spying and then they come back. They are in danger of being shot by their own guards as they try to cross the border.
So you want to have a password mechanism. The assumption is that the spies are high caliber people and can keep a secret. But the border guards go to the local bars and chat---so whatever you tell them will be known to the enemy.
Can you devise an arrangement where the spy will be able to come safely through, but the enemy will not be able to introduce its own spies by using information entrusted to the guards? Press here for a hint.