Re:The puzzle that started complexity theory.
by redwood on Monday December 20, 2010 @08:17PM
(#2026503)
Doesn't anyone else find the solution a bit problematic: sure great concept but unless the guards have a black box tool which is secured and can churn out Y from X, they will have to know the function to prove that Y was congruent with an X...and if they know the function, so too would the enemy. On the other hand if they have a secure tool that does this fine, but this seems to simplify the problem considerably b/c the key is that the guard doesn't need to know anything at all: the tool does all the work.
[ Parent
| on HN ]
Re:The puzzle that started complexity theory.
by shub on Monday December 20, 2010 @09:50PM
(#2026714)
Let f(x) = y. The guards have f and y. A spy gives a guard an x, and the guard computes f(x) and checks it against his list of ys. If it's on the list, the spy can pass. The enemy has f and y too, but it doesn't help them! f(x) is trivial to compute but the inverse is hard, so the enemy knows exactly the answer they want the guard to get and no idea how to make him get it!
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.
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.