Hacker News Reader

Comment by Fargren | Hacker News Reader

The "hint" is the solution. That would be annoying for someone who hadn't figured it out.

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.

The point is that knowing the function doesn't easily yield an X.

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.

One way to have the guard get a particular y is to get him drunk and replace his f with a different one.

In the given example, the careless guards are analogous to a safe, non-malicious recipient connected to an unencrypted channel. In your example, a drunken guard is an unsafe (hackable) client.

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 ;)

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.

Are you saying that the example function is truly a one-way function?

Define "truly one-way"! We don't have any functions that are truly one-way, just very hard to go in the other direction. This is probably easier to reverse than prime factorisation for example, but it's still asymmetric in its difficulty.

Reply on news.ycombinator.com