Comment by Delk
2 days ago
> Remember, a hash is a "one way function". It isn't invertible (that would defeat the purpose!). It is a surjective function. Meaning that reversing the function results in a non-unique output.
This is a bit of a nitpick and not even relevant to the topic, but that's not the reason cryptographic hashes are (assumed to be) one-way functions. You could in principle have a function f: X -> Y that's not invertible but for which the set of every x that give a particular y could be tractably computed given y. In that case f would not be a one-way function in the computational sense.
Cryptographic hashes are practically treated as one-way functions because the inverse computation would take an intractable amount of time.
Yeah that's a good addition. I think often the words we use can really make things more confusing. Like I hate when people say invertible but in reference to a function that isn't bijective. Why not say reversible? (No complaints with the convention of image/preimage)
Which it's very similar to the problem created by saying "one way". It just isn't one way. Going the other direction is perfectly possible but incredibly hard to find the origin. The visual metaphor I like to use for people is it's like you walk out of a room and into a hallway of doors that are all identical looking. Ignoring the fact that you could just physically turn around, it'd be very hard to figure out which one you actually came from.
But maybe what I like least is that we end up having so many terms for the same general concept. It's one thing when they're discovered independently but I'm pretty confident the computer scientists that pioneered hashes were quite familiar with the mathematics and nomenclature.
On a real side note I really like this explanation of P vs NP as it explicitly talks about reversibility. https://m.youtube.com/watch?v=6OPsH8PK7xM