**Exact Maximum Expected Differential and Linear Probability for 2-Round Advanced Encryption Standard (AES)**

*Liam Keliher and Jiayuan Sui*

**Abstract: **Provable security of a block cipher against differential~/ linear
cryptanalysis is based on the \emph{maximum expected differential~/ linear probability} (MEDP~/ MELP) over $T \geq 2$ core rounds.
Over the past few years, several results have provided increasingly
tight upper and lower bounds in the case $T=2$ for the Advanced Encryption Standard (AES). We show that the \emph{exact} value
of the 2-round MEDP~/ MELP for the AES is equal to the best known lower bound: $53/2^{34} \approx 1.656 \times 2^{-29}$~/ $109,953,193/2^{54} \approx 1.638 \times 2^{-28}$.
This immediately yields an improved upper bound on the AES MEDP~/ MELP for $T \geq 4$, namely
$\left( 53/2^{34} \right)^4 \approx 1.881 \times 2^{-114}$~/
$\left( 109,953,193/2^{54} \right)^4 \approx 1.802 \times 2^{-110}$.

**Category / Keywords: **secret-key cryptography / AES, Rijndael, block ciphers, SPN, provable security, differential cryptanalysis, linear cryptanalysis

**Date: **received 10 Sep 2005, last revised 15 Sep 2005

**Contact author: **lkeliher at mta ca

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **Revision to fix problem with PS file. Content unchanged.

**Version: **20050915:185909 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]