Re:The puzzle that started complexity theory.
by kenjackson on Monday December 20, 2010 @03:15PM
(#2025614)
The answers are not recycled. So after given they throw it away.
[ Parent
| on HN ]
Re:The puzzle that started complexity theory.
by losvedir on Monday December 20, 2010 @04:02PM
(#2025761)
I don't see how that solves anything. If the guard knows the answer, then you assume the enemy knows the answer. So all "throwing it away" does, is allow the enemy to cross the border once and the spy stranded!
Re:The puzzle that started complexity theory.
by jamwt on Monday December 20, 2010 @04:11PM
(#2025785)
Well, the guard knows Y, and the enemy knows Y... but the guard's authentication procedure involves taking an X (not Y) supplied by the friendly spy, executing the calculation, and asserting the result is equal to Y. Since the enemy does not know X, and X cannot be trivially derived from Y (one-way function), the scheme is secure.
Re:The puzzle that started complexity theory.
by losvedir on Monday December 20, 2010 @05:40PM
(#2026060)
Yikes, teach me to post when I'm in a hurry! I misunderstood. Thanks for clearing it up.
Re:The puzzle that started complexity theory.
by robinhouston on Monday December 20, 2010 @04:24PM
(#2025824)
Wow, a lot of confusion here!
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.
Re:The puzzle that started complexity theory.
by ernestobad on Monday December 20, 2010 @04:18PM
(#2025805)
The machine is necessary. Although the spy is able to produce a Y number with the machine and the guard knows Y, if the guard doesn't know X he also doesn't know how to generate a Y number with the machine.
Re:The puzzle that started complexity theory.
by brianpan on Monday December 20, 2010 @06:07PM
(#2026129)
Yeah, you have to make a leap that's not explained in the puzzle. An intermediate machine or some other method has to be used to keep the secret a secret, yet the answer can be "public".
Re:The puzzle that started complexity theory.
by InclinedPlane on Monday December 20, 2010 @08:15PM
(#2026499)
The guards don't know the password, they only know how to verify the password.
It's public / private key encryption, or one way hashing.