On the Construction of Low-latency 32 × 32 Binary MDS Matrices from GHadamard Matrices

Abstract

In this paper, we generate new hardware efficient involutory 32 × 32 binary Maximum Distance Separable (MDS) diffusion layers with branch number 5. In our construction method, the idea used in Generalised Hadamard (GHadamard) matrix form is applied when generating these diffusion layers. We construct lightweight circuits by applying Boyar’s global optimization heuristic (BP) to these diffusion layers. Hence, new 32 × 32 binary involutory MDS matrices with the best-known implementation cost (78 XORs) and depth 4 are generated. The obtained result is the same with the previous result given in [1], and we show that the diffusion layer given in [1] can also be obtained directly by using our construction method. As a result, we give thirteen more new involutory 32 × 32 binary MDS matrices with the best-known result.

Keywords

• GHadamard matrix form
• 32 × 32 binary MDS matrix
• Global optimization
• Involutory matrix

References

1. S. Li, S. Sun, C. Li, Z. Wei and L. Hu, Constructing Lowlatency Involutory MDS matrices with Lightweight Circuits, IACR Transactions on Symmetric Cryptology, vol. 1, pp. 84–117, 2019.
2. C.E. Shannon, Communication theory of secrecy systems, Bell Syst. Tech. J., vol. 28, pp. 656-715, 1949.
3. M.K. Pehlivanoğlu and E.B. Kavun, On the Design of Maximum Distance Separable Diffusion Layers of Cryptographic Block Ciphers, in CyberSecurity and Defense, Ankara: Nobel Academic Publishing Education Consultancy, pp. 295-325, 2020.
4. J. Daemen and V. Rijmen, The Design of Rijndael: AES-The Advanced Encryption Standard, 1st ed., Springer-Verlag Berlin Heidelber, pp. 1-7, 2002.
5. J. Guo, T. Peyrin and A. Poschmann, The PHOTON Family of Lightweight Hash Functions, in Advances in Cryptology – CRYPTO 2011, vol. 6841, pp. 222-239, 2011.
6. J. Guo, T. Peyrin, A. Poschmann and M. Robshaw, The LED Block Cipher, in Cryptographic Hardware and Embedded Systems – CHES 2011, vol. 6917, pp. 326-341, 2011.
7. P.S.L.M. Barreto and V. Rijmen, The Khazad Legacy-Level Block Cipher, First Open NESSIE Workshop 2000, Leuven, Belgium, 2000.
8. K. Shibutani, T. Isobe, H. Hiwatari and et al., Piccolo: An Ultra-Lightweight Blockcipher, in Cryptographic Hardware and Embedded Systems – CHES 2011, vol. 6917, pp. 342-357, 2011.

9. C. Paar, Optimized Arithmetic for Reed-Solomon Encoders, 1997 IEEE International Symposium on Information Theory, pp. 250, 1997.
10. J. Boyar and R. Peralta, A New Combinational Logic Minimization Technique with Applications to Cryptology, SEA 2010, LNCS, vol. 6049, pp. 178-189, 2010.
11. J. Boyar, P. Matthews and R. Peralta, Logic Minimization Techniques with Applications to Cryptology, Journal of Cryptology, vol. 26, pp. 280–312, 2013.
12. J. Boyar, M. G. Find and R. Peralta, Low-Depth, Low-Size Circuits for Cryptographic Applications, BFA 2017. 2017.
13. J. Boyar, M. G. Find and R. Peralta, Small Low-depth Circuits for Cryptographic Applications, Cryptography and Communications, vol. 11, no. 1, pp. 109–127, 2019.
14. Q.Q. Tan and T. Peyrin, Improved Heuristics for Short Linear Programs, Cryptology ePrint Archive, Report 2019/847, 2019.
15. C. Wolf, Yosys Open Synthesis Suite, http://www.clifford.at/yosys/, Accessed: November 10, 2021.
16. R.K. Brayton and A. Mishchenko, ABC: An Academic Industrial Strength Verification Tool, CAV 2010, vol. 6174, pp. 24–40, 2010.
17. K. Stoffelen, Optimizing S-Box Implementations for Several Criteria Using SAT Solvers, FSE 2016, LNCS, vol. 9783, pp. 140–160, 2016.
18. J. Jean, T. Peyrin, S.M. Sim and J. Tourteaux, Optimizing Implementations of Lightweight Building Blocks, IACR Trans. Symmetric Cryptol., vol. 2017, no. 4, pp. 130–168, 2017.
19. S. Duval and G. Leurent, MDS Matrices with Lightweight Circuits. IACR Transactions on Symmetric Cryptology, vol. 2018(2), pp. 48-78, 2018.
20. M.K. Pehlivanoğlu, M.T. Sakallı, S. Akleylek, N. Duru and V. Rijmen, Generalisation of Hadamard Matrix to Generate Involutory MDS Matrices for Lightweight Cryptography, IET Information Security, vol. 12, pp. 348–355, 2018.
21. G.G. Guzel, M.T. Sakallı, S. Akleylek, V. Rijmen and Y. C¸ engellenmis¸ A New Matrix Form to Generate All 3 × 3 Involutory MDS Matrices over F2m , Information Processing Letters, vol. 147, pp. 61-68, 2019.
22. M.T. Sakallı, S. Akleylek, K. Akkanat and V. Rijmen, On the automorphisms and isomorphisms of MDS matrices and their efficient implementations, Turkish Journal of Electrical Computer Sciences, vol.28, no. 1, pp. 275-287, 2020.
23. M.K. Pehlivanoğlu, https://github.com/mkurtpehlivanoglu/ 32x32 binarymatrices.git, Accessed: November 11, 2021.
24. T. Kranz, G. Leander, K. Stoffelen and F. Wiemer, Shorterlinear straight-line programs for MDS matrices, IACR Trans. Symmetric Cryptol., vol. 2017(4), pp. 188–211, 2017. 118