The most important cipher in the world today is the Advanced Encryption Standard, AES. It underlies thousands of applications in the economy, communications, archiving, and more, and consequently its security is a matter of great importance. Despite this, no proof of its security has been found to date. On the other hand, no cryptanalytical attack has been successful against properly implemented AES, despite 20 years of attempts.

Block ciphers such as AES are composed of multiple rounds of encryption, each round being simple in itself. Typically a round consists of some sequence of application of the key (by XOR), application of substitution via an S-box function, and a mixing function. Only the key is assumed to be secret, and a sufficient number of rounds is believed to produce output that is indistinguishable from a random string, while still allowing recovery of the original message by a receiver equipped with the key. Block ciphers are fast, highly parallelizable and implementable on chip.

At Upgrade 2021, Professor Stefano Tessaro (University of Washington) reported on joint work with Tianren Liu (University of Washington) and Vinod Vaikuntanathan (MIT) on the theoretical foundations of the security of block ciphers such as AES. Their work takes a different approach to the classical idea of reduction of a known hard problem to breaking of the cipher.

Instead, they measure the indistinguishability of the output of a cipher from a random string of length t by the concept of ε-closeness to t-wise independence. For small ε, this property promises that output strings are statistically very close to random (high entropy). In this way known classes of attacks can be ruled out without ever proving security against all possible attacks.

Tessaro presented technical results on 2-wise independence for various concrete cases, including a non-trivial statistical bound of ε=0.472 for AES with six rounds, block size 8 and key size 128 bits. A standard amplification theorem means that any ε bound is therefore achievable for AES with a sufficient number of rounds. He gave a sketch of the proof methods behind this and other results, with lemmas giving bounds on the increase of entropy to be expected after each round.

Professor Tessaro concluded with remarks placing his team’s work in the context of other approaches and on future work. He emphasized the importance of reuniting the theoretical and cryptanalytical branches of cryptography, which he believes have grown apart, and combining the insights provided by both fields.

Click below for the full transcript.