On the Lower Bound of Cost of MDS Matrices


  • Ayineedi Venkateswarlu Indian Statistical Institute, Chennai Centre, Chennai, India
  • Abhishek Kesarwani IHUB NTIHAC FOUNDATION, IIT Kanpur, Kanpur, India
  • Sumanta Sarkar University of Warwick, Coventry, United Kingdom




Lightweight cryptography, Diffusion layer, MDS matrix, Hardware implementation, XOR cost


Ever since lightweight cryptography emerged as one of the trending topics in symmetric key cryptography, optimizing the implementation cost of MDS matrices has been in the center of attention. In this direction, various metrics like d-XOR, s-XOR and g-XOR have been proposed to mimic the hardware cost. Consequently, efforts also have been made to search for the optimal MDS matrices for dimensions relevant to cryptographic applications according to these metrics. However, finding the optimal MDS matrix in terms of hardware cost still remains an unsolved problem. In this paper, we settle the question of the optimal 4 x 4 MDS matrices over GL(n, F2) under the recently proposed metric sequential XOR count based on words (sw-XOR). We prove that the sw-XOR of such matrices is at least 8n + 3, and the bound is tight as matrices with sw-XOR cost 35 and 67 for the values of n = 4 and 8, respectively, were already known. Moreover, the lower bound for these values of n matches with the known lower bounds according to s-XOR and g-XOR metrics.




How to Cite

Venkateswarlu, A., Kesarwani, A., & Sarkar, S. (2022). On the Lower Bound of Cost of MDS Matrices. IACR Transactions on Symmetric Cryptology, 2022(4), 266–290. https://doi.org/10.46586/tosc.v2022.i4.266-290