International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Beyond-Birthday-Bound Security for 4-round Linear Substitution-Permutation Networks

Authors:
Yuan Gao , School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China
Chun Guo , School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China
Meiqin Wang , School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China
Weijia Wang , School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China
Jiejing Wen , School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China
Download:
DOI: 10.13154/tosc.v2020.i3.305-326
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8704
Search ePrint
Search Google
Abstract: Recent works of Cogliati et al. (CRYPTO 2018) have initiated provable treatments of Substitution-Permutation Networks (SPNs), one of the most popular approach to construct modern blockciphers. Such theoretical SPN models may employ non-linear diffusion layers, which enables beyond-birthday-bound provable security. Though, for the model of real world blockciphers, i.e., SPN models with linear diffusion layers, existing provable results are capped at birthday security up to $2^{n/2}$ adversarial queries, where $n$ is the size of the idealized S-boxes. In this paper, we overcome this birthday barrier and prove that a 4-round SPN with linear diffusion layers and independent round keys is secure up to $2^{2n/3}$ queries. For this, we identify conditions on the linear layers that are sufficient for such security, which, unsurprisingly, turns out to be slightly stronger than Cogliati et al.'s conditions for birthday security. These provides additional theoretic supports for real world SPN blockciphers.
Video from TOSC 2020
BibTeX
@article{tosc-2020-30543,
  title={Beyond-Birthday-Bound Security for 4-round Linear Substitution-Permutation Networks},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={RUB},
  volume={2020, Issue 3},
  pages={305-326},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8704},
  doi={10.13154/tosc.v2020.i3.305-326},
  author={Yuan Gao and Chun Guo and Meiqin Wang and Weijia Wang and Jiejing Wen},
  year=2020
}