New SAT-based model for constructing linear layers with good cryptographic properties and implementation

Abstract

With the rapid growth of Internet of Things (IoT), ensuring the security of devices in resource-constrained environments has become increasingly critical. In this context, the design of lightweight cryptographic algorithms is essential, with a particular emphasis on constructing optimal linear layers to enhance their efficiency and security. An optimal linear layer should simultaneously achieve strong cryptographic properties, while minimizing the number of exclusive OR (XOR) gates required for implementation. Previous research has primarily focused on optimizing existing linear layers. Only a few studies have explored the construction of new linear layers, often employing classical structures such as Feistel and Lai-Massey. However, these studies typically achieve optimality only for specific dimensions or branch numbers. Furthermore, while they aim to construct high-dimensional linear layers, they often result in increased costs for lower-dimensional cases.

In this paper, we present a novel method for constructing optimal linear layers by formulating the problem as a satisfiability (SAT) problem. A major obstacle in previous research was the inability to efficiently search for optimal linear layers as the dimension increased. We overcome this challenge by using our key insight into the relationship between linear layers and the arrangement of XOR gates in their implementation. This understanding allows us to extend the constructible dimension up to 14, significantly beyond what was previously achievable. Moreover, we are able to construct optimal linear layers for arbitrary branch numbers in dimensions ranging from 4 to 12. Finally, we construct linear layers for dimensions ranging from 4 to 14 that match or surpass the best known results in both cryptographic properties and implementation cost. Furthermore, we systematically construct involutory linear layers for dimensions 4 to 14, addressing a gap that has remained open in previous research.

Graphical abstract

Keywords

linear layer / SAT / involutory / binary matrix / XOR gate

References

[1] Yuan Y, Wu W, Shi T, Zhang L, Zhang Y . A framework to improve the implementations of linear layers. IACR Transactions on Symmetric Cryptology, 2024, 2024( 2): 322–347

[2] Li S, Sun S, Li C, Wei Z, Hu L . Constructing low-latency involutory MDS matrices with lightweight circuit. IACR Transactions on Symmetric Cryptology, 2019, 2019( 1): 84–117

[3] Liu Q, Wang W, Fan Y, Wu L, Sun L, Wang M . Towards low-latency implementation of linear layers. IACR Transactions on Symmetric Cryptology, 2022, 2022( 1): 158–182

[4] Biham E, Shamir A . Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology, 1991, 4( 1): 3–72

[5] Matsui M. Linear cryptanalysis method for DES cipher. In: Proceedings of Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology. 1993, 386−397

[6] Paar C. Optimized arithmetic for reed-solomon encoders. In: Proceedings of IEEE International Symposium on Information Theory. 1997, 250

[7] Sim S M, Khoo K, Oggier F, Peyrin T. Lightweight MDS involution matrices. In: Proceedings of the 22nd International Workshop on Fast Software Encryption. 2015, 471−493

[8] Kranz T, Leander G, Stoffelen K, Wiemer F . Shorter linear straight-line programs for MDS matrices. IACR Transactions on Symmetric Cryptology, 2017, 2017( 4): 188–211

[9] Beierle C, Kranz T, Leander G. Lightweight multiplication in GF(2ⁿ) with applications to MDS matrices. In: Proceedings of the 36th Annual International Cryptology Conference on Advances in Cryptology. 2016, 625−653

[10] Liu M, Sim S M. Lightweight MDS generalized circulant matrices. In: Proceedings of the 23rd International Conference on Fast Software Encryption. 2016, 101−120

[11] Li X, Wu W . Constructing binary matrices with good implementation properties for low-latency block ciphers based on Lai-Massey structure. The Computer Journal, 2023, 66( 1): 160–173

[12] Guo Z, Wu W, Gao S. Constructing lightweight optimal diffusion primitives with Feistel structure. In: Proceedings of the 22nd International Conference on Selected Areas in Cryptography. 2015, 352−372

[13] Shi T, Wu W, Hu B, Guan J, Sui H, Wang S, Zhang M . Dedicated quantum attacks on XOR-type function with applications to beyond-birthday- bound MACs. IEEE Transactions on Information Forensics and Security, 2024, 19: 5971–5984

[14] Tan Q Q, Peyrin T . Improved heuristics for short linear programs. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019, 2020( 1): 203–230

[15] Daemen J, Rijmen V. The Design of Rijndael. Berlin, Heidelberg: Springer, 2002

[16] Barreto P, Nikov V, Nikova S, Rijmen V, Tischhauser E . Whirlwind: a new cryptographic hash function. Designs, Codes and Cryptography, 2010, 56( 2−3): 141–162

[17] Aoki K, Ichikawa T, Kanda M, Matsui M, Moriai S, Nakajima J, Tokita T. Camellia: a 128-bit block cipher suitable for multiple platforms-design and analysis. In: Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography. 2000, 39−56

[18] Kwon D, Kim J, Park S, Sung S H, Sohn Y, Song J H, Yeom Y, Yoon E J, Lee S, Lee J, Chee S, Han D, Hong J. New block cipher: ARIA. In: Proceedings of the 6th International Conference on Information Security and Cryptology. 2003, 432−445

[19] Wang Q, Lu J. Fault analysis of the ARIA and uBlock block ciphers. In: Proceedings of 2021 IEEE International Conference on Service Operations and Logistics, and Informatics. 2021, 1−6

[20] Gao Y, Guo G. Unified approach to construct 8X8 binary matrices with branch number 5. In: Proceedings of the 1st ACIS International Symposium on Cryptography, and Network Security, Data Mining and Knowledge Discovery, E-Commerce and Its Applications, and Embedded Systems. 2010, 413−416

[21] Koo B W, Jang H S, Song J H. Constructing and cryptanalysis of a 16 × 16 binary matrix as a diffusion layer. In: Proceedings of the 4th International Workshop on Information Security Applications. 2003, 489−503

[22] Sakallı M T, Akleylek S, Aslan B, Buluş E, Sakallı F B . On the construction of 20 × 20 and 24 × 24 binary matrices with good implementation properties for lightweight block ciphers and hash functions. Mathematical Problems in Engineering, 2014, 2014( 1): 540253

[23] Dehnavi S M, Rishakani A M, Shamsabad M R M. Bitwise linear mappings with good cryptographic properties and efficient implementation. Cryptology ePrint Archive, 2015, 225

[24] Khoo K, Peyrin T, Poschmann A Y, Yap H. FOAM: searching for hardware-optimal SPN structures and components with a fair comparison. In: Proceedings of the 16th International Workshop on Cryptographic Hardware and Embedded Systems. 2014, 433−450

[25] Jean J, Peyrin T, Sim S M, Tourteaux J . Optimizing implementations of lightweight building blocks. IACR Transactions on Symmetric Cryptology, 2017, 2017( 4): 130–168

[26] Xiang Z, Zeng X, Lin D, Bao Z, Zhang S . Optimizing implementations of linear layers. IACR Transactions on Symmetric Cryptology, 2020, 2020( 2): 120–145

[27] Lu Z, Wang W, Hu K, Fan Y, Wu L, Wang M. Pushing the limits: searching for implementations with the smallest area for lightweight S-boxes. In: Proceedings of the 22nd International Conference on Cryptology in India on Progress in Cryptology. 2021, 159−178

[28] Sun L, Wang W, Wang M . Accelerating the search of differential and linear characteristics with the SAT method. IACR Transactions on Symmetric Cryptology, 2021, 2021( 1): 269–315

[29] Jia C, Cui T, Ling Q, He Y, Hu K, Sun Y, Wang M . How small can S-boxes be?. IACR Transactions on Symmetric Cryptology, 2025, 2025( 1): 592–622

[30] Stoffelen K. Optimizing S-box implementations for several criteria using SAT solvers. In: Proceedings of the 23rd International Conference on Fast Software Encryption. 2016, 140−160

[31] Hong H, Jakuš D . Testing positiveness of polynomials. Journal of Automated Reasoning, 1998, 21( 1): 23–38

[32] Fuhs C, Giesl J, Middeldorp A, Schneider-Kamp P, Thiemann R, Zankl H. SAT solving for termination analysis with polynomial interpretations. In: Proceedings of the 10th International Conference on Theory and Applications of Satisfiability Testing. 2007, 340−354

RIGHTS & PERMISSIONS

Higher Education Press