New Techniques for Analyzing Differentials with Application to AES
摘要
We propose new techniques for estimating the probability that an input difference leads to an output difference in a block cipher (i.e., the probability of a differential) under the assumption of independent round-keys. We apply our techniques to AES, and show that the probability of every non-trivial differential in 8-round AES is within an additive factor of \(2^{-128} \cdot \frac{1}{50}\) from the expected value of \(\frac{1}{2^{128} - 1}\) . We further apply our techniques to prove that 40-round AES is at most \(2^{-135}\) -close to a pairwise independent permutation. This improves upon the work of Liu, Tessaro and Vaikuntanathan [CRYPTO 2021], who proved a similar bound for 9000-round AES. To obtain our results, we develop and adapt a variety of techniques for analyzing differentials using functional analysis. We expect these techniques to be useful for analyzing differentials in additional block ciphers besides the AES.