5 ms·
The "hint" is the solution. That would be annoying for someone who hadn't figured it out.
by Fargren 16y ago
The "hint" is the solution. That would be annoying for someone who hadn't figured it out.
- redwood 16y agoDoesn'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.
- mquander 16y agoThe point is that knowing the function doesn't easily yield an X.
- shub 16y agoLet 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.
- nandemo 16y agoAre you saying that the example function is truly a one-way function?
- ZoFreX 16y agoDefine "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.