One-way function vs Non-invertibility

[compSciTchr]

Hi,
I'm trying to understand how these 2 terms differ when discussing hashing and the bitcoin network.
A one-way function to me is a non-invertible function.
Take input A, hash it, get output B
Try to reverse it, good luck

From a cryptographic perspective, are these two terms not similar?
Thank you

[1715122264]

1715122264

[1715122264]

1715122264

[1715122264]

1715122264

[NotATether]

Your description only applies for one-way functions. Non-invertable is something different.

Non-invertable means the inverse of a function does not exist as opposed to merely hard to compute, whether because output values do not exist that will get you the original input, or multiple output values exist. For each input number there must be exactly one unique output value that, when fed to the inverse function, gives you back the input.

For example, 2x is a function that plots a line on a graph and it's inverse would be x/2. But x^2 makes a parabola, and parabolas have the same value for two different inputs, which in this case are +x and -x, so this function cannot be inverted. (No, sqrt(x) is not the inverse since it cannot invert negative inputs as well).

If we were talking about x^2 but only in the range of positive numbers then yes that's investable, it would just be sqrt(x).

I could piece together a function that brute-forces SHA256 and that would be it's inverse, but that doesn't mean it doesn't exist. As stated in the next reply there isn't actually a 1:1 mapping between all outputs and inputs so I guess SHA256 was a bad example to use here.


By the way, where did you hear about non-invertable functions being used in the network?

[j2002ba2]

Non-invertable means the inverse of a function does not exist ...

By this definition sha-256 could be non-invertible as well, depending on its input. And double sha-256 is non-invertible (as used in bitcoin), since half of the possible outputs of the second sha2 are unreachable, and 1/4th have more than one pre-image.

[HeRetiK]

Non-invertable means the inverse of a function does not exist ...

By this definition sha-256 could be non-invertible as well, depending on its input. And double sha-256 is non-invertible (as used in bitcoin), since half of the possible outputs of the second sha2 are unreachable, and 1/4th have more than one pre-image.

I guess in the end this means that SHA256 can only have partial inverses?

https://en.wikipedia.org/wiki/Inverse_function#Partial_inverses

i.e. an inverse function could exist for a set of numbers of size 2^256; or multiple different partial inverses for different sets of numbers. But not one reverse function for all possible inputs, since the domains don't match.

[compSciTchr]

The syllabus we received for a particular bitcoin related unit has these 2 terms so I'm gathering from your responses that they are not similar.

A one-way function may be inverted with enough computing power but a non-invertibility means that no amount of computing power will produce the inverse because information is missing. Would that be correct?

And OWF is basically a hashing function like SHA-256
Where as the concept of non-invertibility may apply to the elliptical curve used for bitcoin wallet generation?

I'm trying to create some context for the students so any specific references to bitcoin will help
Thanks again for the responses

[NotATether]

A one-way function may be inverted with enough computing power but a non-invertibility means that no amount of computing power will produce the inverse because information is missing. Would that be correct?

And OWF is basically a hashing function like SHA-256
Where as the concept of non-invertibility may apply to the elliptical curve used for bitcoin wallet generation?

Yep. Point multiplication is similar to hashing in the sense that it is hard to get the input (the private key) back from it. And half the points on the secp256k1 curve have x- values which do not correspond to a private key number. This implies that point multiplication on secp256k1 is partially invertible, but I could equivalently say that multiplication inside the entire interval of 1..(group order of the curve) is not invertible.

[pooya87]

Point multiplication is similar to hashing in the sense that it is hard to get the input (the private key) back from it.

Not exactly.
EC point multiplication is pure math and there may be some mathematical way found in the future to reverse it but hash functions aren't math, they are more like "chaos" when we take an arbitrary length of bits and throw them around until we get a final fixed length result.

[aliashraf]

For a function, being one-way or irreversible (almost similar concepts) is not enough to be entitled as a hash function, there are at least two other critical tests to pass.

1-Collision Resistance: The function should show very small probability for H(s₁) = H(s₂)

2-Uniformity: For the function's codomain (the set of possible hash values), the probability for each value to be generated by H(s) where s is an arbitrary input, should be evenly distributed. There are tests like chi-squared to evaluate a function's uniformity.

Obviously, Bitcoin hash function, SHA256(2) is an approved hash function for the application as it is irreversible AND passes above tests.