eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2021/507

The t-wise Independence of Substitution-Permutation Networks

Tianren Liu, Stefano Tessaro, and Vinod Vaikuntanathan


Block ciphers such as the Advanced Encryption Standard (Rijndael) are used extensively in practice, yet our understanding of their security continues to be highly incomplete. This paper promotes and continues a research program aimed at *proving* the security of block ciphers against important and well-studied classes of attacks. In particular, we initiate the study of (almost) $t$-wise independence of concrete block-cipher construction paradigms such as substitution-permutation networks and key-alternating ciphers. Sufficiently strong (almost) pairwise independence already suffices to resist (truncated) differential attacks and linear cryptanalysis, and hence this is a relevant and meaningful target. Our results are two-fold. Our first result concerns substitution-permutation networks (SPNs) that model ciphers such as AES. We prove the almost pairwise-independence of an SPN instantiated with concrete S-boxes together with an appropriate linear mixing layer, given sufficiently many rounds and independent sub-keys. Our proof relies on a *characterization* of S-box computation on input differences in terms of sampling output differences from certain subspaces, and a new randomness extraction lemma (which we prove with Fourier-analytic techniques) that establishes when such sampling yields uniformity. We use our techniques in particular to prove almost pairwise-independence for sufficiently many rounds of both the AES block cipher (which uses a variant of the patched inverse function $x \mapsto x^{-1}$ as the $S$-box) and the MiMC block cipher (which uses the cubing function $x \mapsto x^3$ as the $S$-box), assuming independent sub-keys. Secondly, we show that instantiating a key-alternating cipher (which can be thought of as a degenerate case of SPNs) with most permutations gives us (almost) $t$-wise independence in $t + o(t)$ rounds. In order to do this, we use the probabilistic method to develop two new lemmas, an *independence-amplification lemma* and a *distance amplification lemma*, that allow us to reason about the evolution of key-alternating ciphers.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2021
AESinformation theorySubstitution-Permutation NetworkKey-Alternating Cipher
Contact author(s)
tianrenl @ uw edu
tessaro @ cs washington edu
vinodv @ mit edu
2021-07-23: revised
2021-04-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tianren Liu and Stefano Tessaro and Vinod Vaikuntanathan},
      title = {The t-wise Independence of Substitution-Permutation Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2021/507},
      year = {2021},
      doi = {10.1007/978-3-030-84259-8_16},
      note = {\url{https://eprint.iacr.org/2021/507}},
      url = {https://eprint.iacr.org/2021/507}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.