# Any evidence that one way functions exist?

There is no known proof that one way functions exist. But what is the heuristic evidence that they exist?

I sometimes read that the existence of cryptography is heuristic evidence that they exist. E.g. the ciphertext from a block cipher like AES is easily computable if you know the plaintext and key, but the key is not easily computable if you know the plaintext and ciphertext.

This is seen as evidence that AES might be a one way function, but to me it simply suggests that we don't know how to invert AES. In other words, it seems like this is an algorithm-search problem that is very hard (finding the key inversion algorithm), not that that algorithm doesn't exist.

Is my reasoning correct? Whether it is or not, what is the heuristic evidence that one way functions exist?

• Check Section 2.2.4 of Goldreich's book for specific functions suspected to be one-way. – Yuval Filmus Sep 7 '18 at 3:49
• Sure, we don't know how to invert AES efficiently. But the fact that lots of smart people have thought about it and failed to come up with anything is stronger evidence ("less weak evidence", if you prefer) than just "we don't know." Same with P vs NP. – David Richerby Sep 7 '18 at 18:35
• from a theoretical standpoint, reverse-AES algo exists and is obvious, since input and output are fixed-sized (true for any block cipher) – Bulat Sep 7 '18 at 19:56
• @DavidRicherby, but really, it seems to me to be evidence that the invertion-algorithm search problem is hard, not that there is no invertion algorithm. – user56834 Sep 8 '18 at 5:49

Moreover, it is easy to prove that if AES is secure, then the function $F$ defined by
$$F(k) = \text{AES}_K(0)$$
is one-way, where $0$ represents the block of 128 zero bits. To be precise, if AES is a secure PRP, then $F$ is a secure one-way function -- this latter statement can be mathematically proven in a 100% rigorous way. Here by "security" I refer to concrete security rather than asymptotic security. If you're interested in asymptotic security, you'll need something more.
Thus, this is heuristic evidence that one-way functions exist: in particular, we have heuristic evidence that the $F$ defined above is one-way. You can form your own judgement about how persuasive or how strong this evidence is; that probably comes down to a personal judgement.