Paper 2024/083

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

Tianren Liu, Peking University
Angelos Pelecanos, University of California, Berkeley
Stefano Tessaro, University of Washington
Vinod Vaikuntanathan, Massachusetts Institute of Technology

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 randomly and independently chosen and kept 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 we assume 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 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 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.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in CRYPTO 2023
AESinformation theorySubstitution-Permutation Network
Contact author(s)
trl @ pku edu cn
apelecan @ berkeley edu
tessaro @ cs washington edu
vinodv @ mit edu
2024-01-19: approved
2024-01-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tianren Liu and Angelos Pelecanos and Stefano Tessaro and Vinod Vaikuntanathan},
      title = {Layout Graphs, Random Walks and the t-wise Independence of SPN Block Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2024/083},
      year = {2024},
      doi = {10.1007/978-3-031-38548-3_23},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.