News for hackers. Stuff that matters.
Re:The puzzle that started complexity theory. by blahedo on Monday December 20, 2010 @03:16PM (#2025621)
Well, in this formulation, they're one-time passwords; but once the spy is back in the country they could get a fresh one. Of course the more complete solution would be public-key encryption, but they didn't know that yet in 1958---this idea of a one-way function is basically a precursor to that.
Re:The puzzle that started complexity theory. by tzs on Monday December 20, 2010 @04:10PM (#2025781)
A chaining method can be used to reduce the frequency of the guard having to go back for a new password. Let F be the one-way function.

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.

Re:The puzzle that started complexity theory. by eru on Monday December 20, 2010 @04:02PM (#2025758)
And nowadays we would probably use the discrete logarithm problem or factoring integers as the one-way functions of choice.
Re:The puzzle that started complexity theory. by cdavidcash on Monday December 20, 2010 @09:30PM (#2026664)
The suggested solution (modular squaring) already reduces to factoring. http://en.wikipedia.org/wiki/One-way_function#Modular_squari...

(And we'd use a cryptographic hash function anyway.)

Re:The puzzle that started complexity theory. by eru on Tuesday December 21, 2010 @01:50PM (#2028842)
Thanks!
Re:The puzzle that started complexity theory. by sirclueless on Monday December 20, 2010 @11:25PM (#2026939)
No, we probably wouldn't. These one-way functions have some nice properties that we use in RSA and Diffie-hellman, like commutativity and the fact that encryption is a permutation, but these properties come with caveats in that they are considerably easier to break.

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.