News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.