CryptoDB
Layout Graphs, Random Walks and the $t$-wise Independence of SPN Block Ciphers
| Authors: |
|
|---|---|
| Download: |
|
| 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. |
BibTeX
@inproceedings{crypto-2023-33277,
title={Layout Graphs, Random Walks and the $t$-wise Independence of SPN Block Ciphers},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-38548-3_23},
author={Tianren Liu and Angelos Pelecanos and Stefano Tessaro and Vinod Vaikuntanathan},
year=2023
}