Many public-key cryptosystems have some kind of provable security. For example, the Rabin cryptosystem is provably as hard as factoring.I wonder whether such kind of provable security exists for secret-key cryptosystems, such as AES. If not, what is the evidence that breaking such cryptosystems is hard? (other than resistance to trial-and-error attacks)Remark: I'm familiar with AES operations (AddRoundKey, SubBytes, ShiftRows, and MixColumns). It seems that the hardness of AES stems from the MixColumns operation, which in turn must inherit its difficulty from some hard problem over Galois Fields (and thus, algebra). In fact, I can restate my question as: Which hard algebraic problem guarantees the security of AES?
Hardness Guarantees for AES
cr.crypto security;algebra;algebraic complexity
MIXCOLUMNS prevents attacks that focus on only a few S-boxes, because the mixing of the columns requires all S-boxes to participate in the encryption.  (The designers of Rijndael called this a wide trail strategy.)  The reason analysis of an S-box is hard is due to the use of the finite field inversion operation.  The inversion smooths out the distribution tables of S-box entries, so the entries appear (almost) uniform, i.e., indistinguishable from a random distribution without the key.  It's the combination of the two features that makes Rijndael provably secure against known attacks.As an aside, the book The Design of Rijndael is a very good read, and discusses the theory and philosophy of cryptography.