Understanding Pairwise Independence in Cryptography

Pairwise independence may look like a simple probability idea, but it plays an important role in proving the security of block ciphers such as AES.

1. Pairwise Independence and Ideal Permutations

Two random variables are independent if knowing one does not give information about the other. A set of random variables is pairwise independent if every pair is independent, though this does not mean full independence across all of them.

In cryptography, the strongest security goal is an ideal permutation: a cipher that behaves like a perfect random shuffle of all inputs. Real ciphers cannot reach this level, but they can approximate it. One useful approximation is pairwise independence: for any two plaintexts, the ciphertexts should look as if they were produced by a random permutation.

2. Differential Cryptanalysis Background

Differential cryptanalysis (Biham & Shamir 1991) and linear cryptanalysis (Matsui 1993) are two of the most powerful attacks on block ciphers. They were first applied to DES (NIST 1977) and influenced the design of AES (Daemen & Rijmen 1999, 2020), which was built to resist them.

In differential cryptanalysis, the attacker studies how input differences propagate through the cipher and looks for output differences that occur with higher probability than in a random permutation. This probability is estimated using differential characteristics, which describe how the difference moves through each round. The common simplifying assumption is that round keys are independent. Under this assumption, the probability of a characteristic is the product of the probabilities of propagation in each round.

To make analysis easier, the Markov cipher model (Lai, Massey & Murphy 1991) assumes that for almost any fixed key, the probability of a differential characteristic is close to its average probability (over all keys). This assumption is called stochastic equivalence.

3. Pairwise Independence in AES

To go beyond differential analysis, researchers studied closeness to pairwise independence: the distance between AES and an ideal permutation when looking at pairs of encryptions.

Key results show remarkable progress:

  1. Liu, Tessaro & Vaikuntanathan (2021): AES needs about 9,168 rounds to be 2^-128-close to pairwise independence (ePrint 2021/507).

    • The bound was shown as 2^(r−1) * (0.472)^r.

    • Solving for closeness ≤ 2^-128:

      2^(r−1) * (0.472)^r ≤ 2^-128  
r ≈ 1528  
6 * 1528 = 9168

      Thus, 9,168 rounds are needed — a very conservative estimate.

  2. Liu, Patarin, Tessaro & Vaikuntanathan (2023): For a modified AES, 192 rounds are enough for the same closeness.

  3. New Techniques for Analyzing Differentials with Application to AES (2025): Proved that 40-round AES is 2^-135-close to pairwise independence (ePrint 2025/1326).

  4. Pairwise Independence of AES-like Block Ciphers (2025): Extended these results and gave a useful corollary:

    • Corollary 1 (Beyne, T., Leander, G., & Schütt, I):

      ε = 2^(14 – 40r)

      after 4r + 4 rounds.

      Solving for ε ≤ 2^-128:

      2^(14 – 40r) ≤ 2^-128  
40r ≥ 142  
r ≥ 4

      Substituting r = 4 gives 20 rounds.
      Thus, 20 rounds are sufficient to achieve pairwise independence at the 2^-128 level.

From 9,168 rounds, down to 192, then 40, and finally 24 rounds under certain assumptions, these results show how proofs have become dramatically sharper. This does not mean AES should change its 10/12/14-round structure; rather, it shows theoretical analysis is catching up with practice, giving stronger confidence that AES behaves very close to an ideal random permutation when measured by pairwise independence.

4. Pairwise Independence: Assumptions, Exceptions, and Summary

Pairwise independence works best under the key-averaged model: round keys are assumed to be independent and random. Under this assumption, AES behaves almost like a random permutation, making differential probabilities extremely low on average. This directly blocks classical differential attacks, which rely on finding high-probability differences across many encryptions.

However, pairwise independence guarantees only average-case security. It does not ensure that every key is equally strong. Some keys may still be weak and show unusually high differential probabilities. Modern research introduced quasidifferential analysis, which studies key-dependent probabilities and shows that reduced-round AES may admit such weaknesses.

Summary:

  • ✅ Pairwise independence is weaker than full independence but provides valuable security guarantees.
  • ✅ AES differential security is partly proven, with proofs sharpening over time.
  • ✅ Bounds improved dramatically: 9,168 → 192 → 40 → 20 rounds.
  • ⚠️ Pairwise independence covers average-case security only; quasidifferential analysis exposes possible weak keys.
  • ✅ AES remains practically strong, and theory continues to align more closely with observed security.

References

  1. Liu, J., Tessaro, S., & Vaikuntanathan, V. (2021). The t-wise Independence of Substitution–Permutation Networks. IACR ePrint 2021/507. https://eprint.iacr.org/2021/507
  2. Liu, M., Patarin, J., Tessaro, S., & Vaikuntanathan, V. (2023). Improved Bounds on the t-wise Independence of SPNs. IACR ePrint 2023.
  3. Dinur, I. (2025). New Techniques for Analyzing Differentials with Application to AES. IACR ePrint 2025/1326. https://eprint.iacr.org/2025/1326
  4. Beyne, T., Leander, G., & Schütt, I. (2025). Pairwise Independence of AES-like Block Ciphers. IACR ePrint 2025/1495. https://eprint.iacr.org/2025/1495
  5. Keliher, L., & Sui, J. (2005). Exact MEDP Bounds for 4-Round AES.
  6. Knudsen, L.R., & Nyberg, K. (1992, 1995). Provable Security Against Differential Cryptanalysis.