6
$\begingroup$

I was recently going through the Wiki page List of unsolved Problems in Computer Science.

There was a problem which I do not understand

Do one-way functions exist ? [Is public-key cryptography possible ?]

A one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input.

A one-way function that comes to mind is a Cryptographic hash function which is used to create message digests. Where size of the message digest is relatively small as compared to the size of the message and hence it becomes very hard to reconstruct message from the message digest.

So, why does the above problem say that these functions do not exist?

$\endgroup$
1
  • $\begingroup$ Hashing is slightly different. Hashing is not bijective, so you cannot find the original but only some possible original in the best case. $\endgroup$
    – gnasher729
    Jul 29, 2022 at 17:28

2 Answers 2

8
$\begingroup$

No known cryptographic hash functions are provably secure. It might seem to be hard to reconstruct an input hashing to a given hash value, but we can't prove that it is indeed very hard. We can just say that no one was able to find an algorithm accomplishing that so far, but there is no guarantee that tomorrow such an algorithm won't be found.

In cryptography there is a very exact definition of one-way functions, which implies, among else, that P$\neq$NP. While there are several specific functions which are conjectured to satisfy the definition, no one knows how to prove this. We don't even know how to prove that one-way functions exist assuming P$\neq$NP.

$\endgroup$
0
0
$\begingroup$

Your question is a loaded question. The example of the message digest doesn't prove that these functions do not exist. It only proves that there is no discernable system key from which to construct the entire message from the message digest. For example consider a system that uses check digits for license plates or social security numbers to eliminate errors or fake plates.

or suppose the message digest was the number "1" and the whole message was a larger three digit number, let's say "247"... We could get there by...

1 2 {1} 3 2 {2} 4 {3} 7 247 or a SS# with a check-digit of "0" might be recreated or confirmed possibly real... 0
11 00,11,22,33,44,55,66,77,88,99 choose 1 101
1001 32221 413134 1541251 23843501 4 {2} 6 {3} 9… etc. 469158334 the final level check

238458334 next level 4 {2} 6 {3} 9 {8} 1 {4} 5 {3} 8 {5} 3 {0} 3 {1} 4
469158334

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.