International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Provable Security of SP Networks with Partial Non-Linear Layers

Authors:
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 Lab
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 Lab
Xiao Wang , Northwestern University, Evanston, Illinois, USA
Yu Yu , Shanghai Jiao Tong University, Shanghai, China
Download:
DOI: 10.46586/tosc.v2021.i2.353-388
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8914
Search ePrint
Search Google
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.
Video from TOSC 2021
BibTeX
@article{tosc-2021-31089,
  title={Provable Security of SP Networks with Partial Non-Linear Layers},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2021, Issue 2},
  pages={353-388},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8914},
  doi={10.46586/tosc.v2021.i2.353-388},
  author={Chun Guo and François-Xavier Standaert and Weijia Wang and Xiao Wang and Yu Yu},
  year=2021
}