Presentation of a Method for Implementing Binary Matrices and its Application in the Implementation of MDS Matrices

Subject Areas : Communication Engineering

Mohsen Mousavi ¹ (Faculty of Applied Sciences, Malek-Ashtar University of Technology, Isfahan, Iran)

Received: 2022-02-28 Accepted : 2022-06-16 Published : 2022-05-22

Keywords: Heuristics Algorithms, Implementation of Binary Matrices, MDS Matrix,

Abstract :

MDS matrices have a crucial role in the cryptography and coding theory. MDS matrices are used as the diffusion layer in cryptosystems as well as in the construction of linear codes with the maximum error correction capability. On the one hand, the entries of MDS matrices are elements of finite fields. On the other hand, it is a major issue to implement finite fields in the lightweight cryptography. Therefore, to use MDS matrices in the lightweight cryptography, these matrices are first converted to binary matrices and then implemented using heuristics algorithms. In this paper, a method to implement binary matrices with low-cost XOR is proposed and then using the proposed method, a heuristics algorithm for implementing MDS matrices is introduced. The structure of the proposed heuristics algorithm is based on the assumption that let A be a binary matrix (or the binary form of an MDS matrix). First, using a random-iterative method, we obtain a list S from a binary matrix A. Then, based on the list S, we construct a binary matrix B. Next, we find a relation between the implementations of A and B. In other words, using the implementation of the matrix B, we get a low-cost implementation for the matrix A. In the structure of the proposed heuristics algorithm, one of the familiar SLP algorithms called Paar is applied.

References:

[1] K. C. Gupta, S.K. Pandey, I.G. Ray and S. Samanta, “Cryptographically significant MDS matrices over finite fields: A brief survey and some generalized results,” Advances in Mathematics of Communications, vol. 13, no. 4, pp. 779-843, 2019, Doi: 10.3934/amc.2019045.

[2] L. Kolsch, “XOR-Counts and Lightweight Multiplication with Fixed Elements in Binary Finite Fields,” Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 285–312, 2019, Doi: 10.1007/978-3-030-17653-2_10.

[3] C. Paar, “Optimized arithmetic for Reed-Solomon encoders,” Proceedings of IEEE International Symposium on Information Theory, pp. 250-250, Jun. 1997, Doi: 10.1109/ISIT.1997.613165.

[4] J. Boyar, P. Matthews and R. Peralta, “Logic Minimization Techniques with Applications to Cryptology,” Journal of Cryptology, vol. 26, no. 2, pp. 280-312, Apr. 2013, Doi: 10.1007/s00145-012-9124-7.

[5] S. Banik, Y. Funabiki and T. Isobe, “More Results on Shortest Linear Programs,” International Workshop on Security, pp. 109-128, Jul. 2019, Doi: 10.1007/978-3-030-26834-3_7.

[6] Q. Q. Tan and T. Peyrin, “Improved Heuristics for Short Linear Programs,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2020, no. 1, pp. 203-230, Nov. 2019, Doi: 10.13154/tches.v2020.i1.203-230.

[7] F. J. MacWilliams and N.J.A. Sloane, “The Theory of Error Correcting Codes,” NorthHolland, 1977.

[8] H. Kranz, G. Leander, K. Stoffelen and F. Wiemer, “Shorter Linear Straight-Line Programs for MDS Matrices,” IACR Transactions on Symmetric Cryptology, vol. 2017, no. 4, pp. 188-211, Nov. 2017, Doi: 10.13154/tosc.v2017.i4.188-211.

[9] M. Mousavi, (2020), GitHub repository, https://github.com/mousavi-codes/Implementation-of-Binary-Matrices.

[10] J. Daemen and V. Rijmen, “The Design of Rijndael: AES-The Advanced Encryption Standard,” Springer-Verlag, 2002, Doi: 10.1007/978-3-662-04722-4.

[11] Q. Liu, W. Wang, Y. Fan, L. Wu, L. Sun and M. Wang, “Towards Low-Latency Implementation of Linear Layers,” IACR Transactions on Symmetric Cryptology, vol. 2022, pp. 158-182, Mar. 2022, Doi: 10.46586/tosc.v2022.i1.158-182.

[12] S. Sarkar, and H. Syed, “Analysis of Toeplitz MDS matrices,” Australasian Conference on Information Security and Privacy, vol. 10343, pp. 3-18, May. 2017, Doi: 10.1007/978-3-319-59870-3_1.

[13] P. Barreto and V. Rijmen, “The Khazad Legacy-Level Block Cipher,” In Proceedings of the first open NESSIE Workshop, Belgium, Nov. 2000.

[14] S. M. Sim, K. Khoo, F. Oggier and T. Peyrin, “Lightweight MDS Involution Matrices,” International Workshop on Fast Software Encryption, vol. 9054, pp. 471-493, Mar. 2015, Doi: 10.1007/978-3-662-48116-5_23.