Can irreversibility of trapdoor functions generally not be proved?

Question

The German Wikipedia article on asymmetric cryptography states that asymmetric cryptography is always based on assumptions which can not be proven:

Die Sicherheit aller asymmetrischen Kryptosysteme beruht also immer auf unbewiesenen Annahmen.

translation: Thus, the security of all asymmetric cryptosystems is always based on unproven assumptions.

I could not find any confirmation for this statement in other sources.

• is this statement correct?
• or is it wrong, i.e. while there is no proof for the irreversibility of trapdoor functions yet, it can't be ruled out that there may be a proof that e.g. the prime factorization or discrete logarithm are irreversible functions?

I don't have a strong math background, but e.g. a simple module operation is obviously not reversible because the same result can be achieved with different numbers.

• 5 mod 3 = 2
• 8 mod 3 = 2

So for modulo, a proof of irreversibility exists. (Now, afaik, a modulo-operation is a one-way function but not a trapdoor function - and maybe that's a crucial difference for such a statement of is unprovable).

Update:

Some clarification: How I read this statement is that always does not refer only to the current knowledge, but says that asymmetric cryptography with trapdoor functions is and will generally always be based on unproven assumptions (i.e. it is generally not possible to find a trapdoor function and prove it is irreversible).

Answer 1

This seems to be an open research problem. If you look at https://en.wikipedia.org/wiki/One-way_function it says that the existence of one-way functions is currently unproven. So for cryptography applications there are two pieces missing for a rigorous proof. First, one-way functions do exist and second, the particular function used in the cryptographic algorithm is such a one-way function.

Edit: I would say that the statement using 'always' on the German wikipedia is wrong. With current knowledge it is based on unproven assumptions. If at some later time it is proven that one-way functions exist one could prove the security of public key cryptography. If on the other hand it is shown that no one-way functions exists, this proves that all public key cryptography is a priori unsecure. It might just be the case that we don't know how to invert a particular function even though we know it can't be a one-way function.

Answer 2

This is due to the fact that the existence of One-Way Functions (OWF) implies that $P \neq NP$. In other words, with contrapositive, if $P = NP$ then OWF doesn't exit. So if we have one you would know it in the news. Therefore, the security of the cryptographic systems is based on unproven results.

There are candidates for OWF functions like;

• Multiplication and Factoring
• The Rabin function used in Rabin Cryptosystem
• Discrete logarithms used in ECC, ElGamal encryption, DHKE
• Cryptographically secure hash functions

After extensive research, these are neither proven as an OWF or the reverse.

• As of Sep. 2021, there is an advancement in this area by Yanyi Liu and Rafael Pass

  • On One-way Functions and Kolmogorov Complexity.

    This is an existence result. A nice introduction is on the Quanta magazine