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

Authors

  • 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

DOI:

https://doi.org/10.13154/tosc.v2020.i3.305-326

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.

Downloads

Published

2020-09-28

Issue

Volume 2020, Issue 3

Section

Articles

License

Copyright (c) 2020 Yuan Gao, Chun Guo, Meiqin Wang, Weijia Wang, Jiejing Wen

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

Beyond-Birthday-Bound Security for 4-round Linear Substitution-Permutation Networks. (2020). IACR Transactions on Symmetric Cryptology, 2020(3), 305-326. https://doi.org/10.13154/tosc.v2020.i3.305-326