Provable Security of SP Networks with Partial Non-Linear Layers

Guo, Chun [ School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237, China] Standaert, François-Xavier [UCL] Wang, Weijia [ School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237, China] Wang, Xiao [Northwestern University, Evanston, Illinois, USA] Yu, Yu [Shanghai Jiao Tong University, Shanghai, China]

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.