3 ms·
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
by shub 16y ago
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.
- artsrc 16y agoOne way to have the guard get a particular y is to get him drunk and replace his f with a different one.
- nandemo 16y agoIn 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.
- colanderman 16y agoWhat 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 ;)
- nandemo 16y agoThey 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.