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

  • Yuan Gao School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237, China; Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, Shandong, 266237, China
  • Chun Guo School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237, China; Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, Shandong, 266237, China; State Key Laboratory of Information Security (Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China)
  • Meiqin Wang School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237, China; Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, Shandong, 266237, China
  • Weijia Wang School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237, China; Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, Shandong, 266237, China; State Key Laboratory of Information Security (Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China)
  • Jiejing Wen School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237, China; Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, Shandong, 266237, China
Keywords: blockciphers, substitution-permutation networks, beyond-birthdaybound

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 2n/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 22n/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.

Published
2020-09-28
How to Cite
Gao, Y., Guo, C., Wang, M., Wang, W., & Wen, J. (2020). Beyond-Birthday-Bound Security for 4-round Linear Substitution-Permutation Networks. IACR Transactions on Symmetric Cryptology, 2020(3), 305-326. https://doi.org/10.13154/tosc.v2020.i3.305-326
Section
Articles