Re:The puzzle that started complexity theory.
by colanderman on Tuesday December 21, 2010 @02:50AM
(#2027268)
What I don't get is: if the guards aren't to be trusted, how can the spies safely tell them x?
I suppose this is why public-key cryptography was invented ;)
Re:The puzzle that started complexity theory.
by nandemo on Tuesday December 21, 2010 @03:52AM
(#2027358)
They can throw x away after using it. Alternatively, they can cross the y off their list after matching it (making it a one-time password).
The idea is that the guards aren't malicious, just stupid.
Re:The puzzle that started complexity theory.
by artsrc on Monday December 20, 2010 @11:40PM
(#2026969)
One way to have the guard get a particular y is to get him drunk and replace his f with a different one.
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.