Construction of a "simple", nothing-up-my-sleeves, provably KPA resistant symmetric cipher

Question

Why is AES secure? Apparently there is no answer - Why is AES resistant to known-plaintext attacks?.

With this in mind, one would obviously want a cipher that is mathematically provable to be resistant to KPA. How would one go about constructing such a cipher? Has it been done? Can it be done? Is someone doing it? Why hasn't it been done? Can you blame mathematics atleast?

When I look at AES, I see a bunch of random up-the-sleeves operations, with, as aforementioned, mostly no explanation. Why can't there be a simple, efficient and secure algorithm to encrypt things?

Imagine a simple (e.g. xor) cipher with a 256-bit key that is applied to each 256 bit aligned block of the plaintext. Suppose it wasn't vulnerable to KPA and other attacks. Then it would be equally secure as AES-256, if not better, given the potential flaws of AES. Problem solved? Unfortunately not; contradiction.

Answer 1

With this in mind, one would obviously want a cipher that is mathematically provable to be resistant to KPA.

Any scheme that has a message space larger than the key space and is unconditionally provably resistant against known-plaintext attacks while being efficiently computable immediately implies $P\neq NP$. As we don't know for sure whether $P\neq NP$ holds and this having been a famously tricky question to answer it seems like it is really hard to build such a cipher.

However if you're willing to make assumptions, we know provably secure constructions. The issue with that is though that most of these assumptions and constructions lead to ciphers that offer no real security advantage over a heuristically well-designed cipher like AES while being much much slower.

When I look at AES, I see a bunch of random up-the-sleeves operations, with, as aforementioned, mostly no explanation.

While this may look to be the case at first glance, the design of AES was very considerate. If you wish to learn more about this topic I suggest you read the book on why AES looks the way it does: "The Design of Rijndael" by Rijndael and Daemen.

Answer 2

How would one go about constructing such a cipher? Has it been done? Can it be done?

If you have a key which is at least as long as the message (and don't reuse the key to encrypt a second message), we know how to do that (and it isn't that hard). Other than that, no, we don't know how to do it; we don't even know that it can be done.

The closest we can get is to create a cipher where, if you can break it, you can solve some other generally accepted hard problem (say, factoring a large composite number). On the other hand, that is just shifting the problem, as we can't prove that factoring large composite numbers is actually harder than breaking, say, AES-256.

When I look at AES, I see a bunch of random up-the-sleeves operations, with, as aforementioned, mostly no explanation.

Actually, the AES team published their justifications for their operations; they selected their operations to be provably resistant to a number of generic attacks (differential, linear and saturation cryptanalysis). Of course, since they can't prove that their structure isn't vulnerable to unknown attacks, they haven't proven that they are KPA (and so they're just like every other small key cipher).