Although this does give an interesting intuition for a one way function, the application is wrong. Per the article, Alice doesn't want to leak any information

Although this does give an interesting intuition for a one way function, the application is wrong. Per the article, Alice doesn't want to leak any information about the solution. Simply using a one way function allows Bob to check if one of a possible set of solutions is valid. ( He can just evaluate f on the finite set of answers). It also can leak a bunch of other information, provided it doesn't give the solution in its entirety. For example, f(x) =x^2 mod N is a one way function if factoring is hard. However, it's only hard to learn some log(log(N)) bits of X, the rest is believed to be easy ( and know to be for certain bits). What Alice wants is a commitment scheme[0] which has some secret randomized input. She would commit to her solution, send it to Bob, wait until Bob has solved the puzzle or gives up, and then prove that she had the solution first by providing both the solution and the randomness. Now you can construct a commitment scheme from a one way function, but a one way function is not a commitment scheme. Now if they both just want to check if they have the same solution, you have to do far more complex than either of these involving Secure Multi Party Computation. [0] http://en.wikipedia.org/wiki/Commitment_scheme http://en.wikipedia.org/wiki/Commitment_scheme