4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Check Section 2.2.4 of Goldreich's book for specific functions suspected to be one-way. $\endgroup$
    – Yuval Filmus
    Commented Sep 7, 2018 at 3:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Commented Sep 7, 2018 at 18:35
  • $\begingroup$ from a theoretical standpoint, reverse-AES algo exists and is obvious, since input and output are fixed-sized (true for any block cipher) $\endgroup$
    – Bulat
    Commented Sep 7, 2018 at 19:56
  • $\begingroup$ @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. $\endgroup$
    – user56834
    Commented Sep 8, 2018 at 5:49

1 Answer 1

Reset to default
3
$\begingroup$

AES is widely believed to be secure: many smart people have tried to break it and haven't been able. This is not a proof, and it is arguable exactly how strong this evidence is, but it does count as heuristic evidence of some sort. The fact that we haven't been able to find an algorithm to break AES does seem to count as some sort of heuristic evidence that no such algorithm exists -- again, not ironclad, not a proof, arguable how strong the evidence is, some might even call it weak evidence, but still evidence of some sort.

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ AES is defined on an input of constant size. You need a family of functions defined on arbitrarily large inputs. $\endgroup$
    – Yuval Filmus
    Commented Sep 9, 2018 at 2:03
  • $\begingroup$ @YuvalFilmus, good point, I've edited my answer to reflect that. $\endgroup$
    – D.W. ♦
    Commented Sep 9, 2018 at 4:08

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.