Welcome to the resource topic for 2024/083
Title:
Layout Graphs, Random Walks and the t-wise Independence of SPN Block Ciphers
Authors: Tianren Liu, Angelos Pelecanos, Stefano Tessaro, Vinod Vaikuntanathan
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 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.
ePrint: https://eprint.iacr.org/2024/083
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .