Provable Security of SP Networks with Partial Non-Linear Layers

  • 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)
  • François-Xavier Standaert ICTEAM/ELEN/Crypto Group, UCLouvain, Louvain-la-Neuve, Belgium
  • 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)
  • Xiao Wang Northwestern University, Evanston, Illinois, USA
  • Yu Yu Shanghai Jiao Tong University, Shanghai, China
Keywords: blockciphers, substitution-permutation networks, provable security, LowMC, low multiplicative complexity

Abstract

Motivated by the recent trend towards low multiplicative complexity blockciphers (e.g., Zorro, CHES 2013; LowMC, EUROCRYPT 2015; HADES, EUROCRYPT 2020; MALICIOUS, CRYPTO 2020), we study their underlying structure partial SPNs, i.e., Substitution-Permutation Networks (SPNs) with parts of the substitution layer replaced by an identity mapping, and put forward the first provable security analysis for such partial SPNs built upon dedicated linear layers. For different instances of partial SPNs using MDS linear layers, we establish strong pseudorandom security as well as practical provable security against impossible differential attacks. By extending the well-established MDS code-based idea, we also propose the first principled design of linear layers that ensures optimal differential propagation. Our results formally confirm the conjecture that partial SPNs achieve the same security as normal SPNs while consuming less non-linearity, in a well-established framework.

Published
2021-06-11
How to Cite
Guo, C., Standaert, F.-X., Wang, W., Wang, X., & Yu, Y. (2021). Provable Security of SP Networks with Partial Non-Linear Layers. IACR Transactions on Symmetric Cryptology, 2021(2), 353-388. https://doi.org/10.46586/tosc.v2021.i2.353-388
Section
Articles