4
$\begingroup$

I have taken a course in applied Cryptography. I do not understand the hardness problem underlying AES (or DES).

As in RSA is based on the RSA assumption. ElGamal is based on the hardness of descrete logarithm problem. Most of the lattice crypto is based on the LWE assumption which itself is based on the hardness of BDD problem. What is the hardness problem that guaranties the security of AES? (Or DES)

In other words if there is an oracle R that can break AES. Can I use this oracle as a subroutine to solve some really hard problem? If yes, what is the reduction?

| improve this question | |
$\endgroup$
3
$\begingroup$

No, there is no reduction from AES to any well-known hardness assumption; in other words, the hypothesis that AES is secure is an assumption by itself.

In fact, this is the case for every practical symmetric cipher that you can think off; provable constructions from a one-way function would be completely impractical.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Every practical symmetric cipher. $\endgroup$ – Stephen Touset Feb 28 '17 at 19:49
  • 1
    $\begingroup$ On the other hand, I'm not sure why "the AES problem" is not considered a valid hard problem, while "the RSA problem" is. $\endgroup$ – poncho Feb 28 '17 at 21:44
  • 1
    $\begingroup$ It is a valid hard problem, and a very hard one indeed. But the algebraic nature of RSA makes it suitable as a hardness assumption that will underly a large variety of very different constructions - encryption schemes, signatures, zero-knowledge proofs, protocols, all coming in several flavors depending on the security notions you consider. Therefore, it allows to argue that many different primitives are "equivalently secure". The security of AES is fine, but there is a considerably lower number of primitives whose security reduces to that of AES, so it looks "less generic" in some sense. $\endgroup$ – Geoffroy Couteau Feb 28 '17 at 21:52
  • $\begingroup$ In fact DES was also considered hard once upon a time. As there were no hard problems underlying it was broken in due time. $\endgroup$ – user38956 Mar 4 '17 at 5:15
  • $\begingroup$ That's a bit tautological: if a cipher is broken, then by definition, the underlying hard problem was not secure; if a cipher is not broken, then the underlying problem might be secure. A reduction does not make it more secure, it only allows to use the same underlying problem for different primitives, to save cryptanalytic effort. I once came upon a cryptosystem which had a nice reduction to a variant of DDH; the reduction worked right, but the variant of DDH was insecure, and the cryptosystem was too. AES has no reduction, but has been studied a lot and seems as secure as a cipher can be. $\endgroup$ – Geoffroy Couteau Mar 4 '17 at 10:26