Hacker News new | ask | show | jobs
by CloselyChunky 1962 days ago
Small nitpick: The existence of one-way functions has not been proven, yet. Actually proving this would also prove `P != NP` so this would be a big deal (interestingly enough, proving that one-way functions do _NOT_ exist, would _NOT_ prove that `P = NP`). Currently we can only assume and hope, they exist.
1 comments
karmakaze 1962 days ago
What do you mean by one-way functions? If there are more possible inputs than outputs, then it's not reversible.
link
CloselyChunky 1962 days ago
This is in reference to "Hashes cannot be undone".

One-way functions are functions that are easily computed given any input but where it is hard/impossible to compute the/a input if you only know the output. This is the property of hash functions that we make use of when hashing passwords, generating signatures, validating files and so on.

We assume that hash functions are one-way functions but to prove the existence of one-way functions is one of the big unsolved problems in computer science. Additionally it has been shown that if one-way functions exist, that P != NP.

With that in mind, we cannot confidently say that "Hashes cannot be undone". While it might still be impossible to find the exact input that was used (unlimited input range vs limited output range), it would be possible to find a possible input resulting in the output you are looking at.

The Wikipedia article [0] is a good starting point for more information.

[0]: https://en.wikipedia.org/wiki/One-way_function

link
karmakaze 1961 days ago
Got it. I see the distinction. Undone as in find an input that produces a specific hash vs finding the input that originally made the hash. And we rely on not being able to do either efficiently.

From Wikipedia:

> It is not sufficient to make a function "lossy" (not one-to-one) to have a one-way function. In particular, the function that outputs the string of n zeros on any input of length n is not a one-way function because it is easy to come up with an input that will result in the same output. More precisely: For such a function that simply outputs a string of zeroes, an algorithm F that just outputs any string of length n on input f(x) will "find" a proper preimage of the output, even if it is not the input which was originally used to find the output string.

link