The puzzle that started complexity theory.
cs.nyu.edu
cs.nyu.edu
One-way functions are very cool and form the basis of public-key cryptography, although it's quite a bit more complicated than this example.
I suppose this is why public-key cryptography was invented ;)
The idea is that the guards aren't malicious, just stupid.
The idea is that X is the credential, and Y is a sort of digital signature of X.
So the spy knows X, and the border guard has a record of Y. When the spy wants to cross the border, he tells the guard X, and the guard can check that the credential is legitimate by seeing whether it matches the signature Y.
It's public / private key encryption, or one way hashing.
(And we'd use a cryptographic hash function anyway.)
A simple consequence is that we need something like 1024 bits for a strong RSA key, but SHA-256 is still miles out of reach of being attackable.
You give the spy a value x0. Then you compute x1=F(x0), x2=F(x1), ..., x_n = F(x_{n-1}). The guard is given x_n.
When the guard challenges the spy, the guard gives the spy x_n, the spy iterates F starting on x0 until he finds x_{n-1}, and gives that to the guard, who checks it.
The guard then replaces x_n with x_{n-1} and uses that for the next challenge, and so on. This allows for n border crossings before the spy and guard need to come to headquarters for new numbers.
Each spy can either have his own x_0, in which case the guard has to have an x_n for each spy, or you can have all the spies share the same x_0, or you can do something in between such as having the less important spies share a value and have your most important spies have their own values.
http://blog.computationalcomplexity.org/2006/04/kurt-gdel-19...
Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists