Theoretical Foundations of Block Ciphers

Block ciphers are the workhorses of modern cryptography. An overwhelming fraction of the Internet traffic is encrypted and secured using the Advanced Encryption Standard (AES), a block cipher; the same goes for encrypted file systems, encrypted messaging, and several other applications that we use in our everyday life. This research theme aims to advance the foundational understanding of the security of block ciphers such as AES.

For one, we have the formidable machinery of theoretical cryptography which aims to reduce the security of cryptographic constructions (such as AES) to the hardness of well-studied computational and mathematical problems. However, AES derives its security from iterating several times a simple permutation which, by itself, does not have any discernible cryptographic hardness. Thus, the reductionist machinery gets stuck right off the bat: What even is a mathematical problem from which to deduce the security of AES?

Secondly, a different line of work analyzes constructions in idealized models where certain components are treated as public random primitives, a classical example being the analysis of the Even-Mansour construction of a block cipher from a public ideal random permutation. While insightful, this scenario is far from what happens in the design of AES: the only non-linear component in AES is the 8-bit S-box which essentially computes the inverse function over the finite field $\mathbb{F}_{2^8}$. This is decidedly not a random permutation with an exponentially large domain, something that all such analyses (to our knowledge) assume.

Finally, the cryptanalytic community has come up with an extensive body of attacks including linear and differential attacks, higher-order attacks, and algebraic attacks. These attacks have so far failed to make a dent in the conjectured security of AES as a pseudorandom permutation (except for limited results in the case of reduced-round variants, or in non-standard settings such as related-key attacks). While this is perhaps great news (so far) for the practice of cryptography, it is still entirely possible that a small, clever, variant of known attacks breaks AES in a devastating way.

We explore a different, bottom-up, approach. Our goal is to analyze existing construction paradigms for block ciphers as well as design new ones that enjoy rigorous proofs of security against specific, yet powerful and commonly deployed classes of attacks.