International Association for Cryptologic Research

International Association
for Cryptologic Research


Layout Graphs, Random Walks and the $t$-wise Independence of SPN Block Ciphers

Tianren Liu , Peking University
Angelos Pelecanos , UC Berkeley
Stefano Tessaro , University of Washington
Vinod Vaikuntanathan , MIT
DOI: 10.1007/978-3-031-38548-3_23 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: We continue the study of $t$-wise independence of substitution-permutation networks (SPNs) initiated by the recent work of Liu, Tessaro, and Vaikuntanathan (CRYPTO 2021). Our key technical result shows that when the S-boxes are {\em randomly and independently chosen}, as well as secret, an $r$-round SPN with input length $n = b \cdot k$ is $2^{-\Theta(n)}$-close to $t$-wise independent within $r = O(\min\{k, \log t\})$ rounds for any $t$ almost as large as $2^{b/2}$. Here, $b$ is the input length of the S-box and the result assumes that the underlying mixing achieves maximum branch number. We also analyze the special case of AES parameters (with random S-boxes), and show it is $2^{-128}$-close to pairwise independent in $7$ rounds. Central to our result is the analysis of a random walk on what we call the {\em layout graph}, a combinatorial abstraction that captures equality and inequality constraints among multiple SPN evaluations. We use our technical result to show concrete security bounds for SPNs with actual block cipher parameters and {\em small-input $S$-boxes}. (This is in contrast to the large body of results on ideal-model analyses of SPNs.) For example, for the censored-AES block cipher, namely AES with most of the mixing layers removed, we show that 192 rounds suffice to attain $2^{-128}$-closeness to pairwise independence. The prior such result for AES (Liu, Tessaro and Vaikuntanathan, CRYPTO 2021) required more than 9000 rounds.
  title={Layout Graphs, Random Walks and the $t$-wise Independence of SPN Block Ciphers},
  author={Tianren Liu and Angelos Pelecanos and Stefano Tessaro and Vinod Vaikuntanathan},