Paper 2021/507

The t-wise Independence of Substitution-Permutation Networks

Tianren Liu and Stefano Tessaro and Vinod Vaikuntanathan

Abstract

This paper promotes and continues a research program aimed at proving the security of block ciphers such as AES 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. This is a meaningful target, as sufficiently strong (almost) pairwise independence already suffices to resist (truncated) differential attacks and linear cryptanalysis. Our results are two-fold. - Our first result concerns substitution-permutation networks (SPNs) that model block ciphers such as AES. We prove the almost pairwise-independence of an SPN instantiated with a concrete S-box such as the patched inverse function $x \mapsto x^{-1}$ as well as 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 sub-spaces, 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 AES rounds, 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.