International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: 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
DOI: 10.46586/tosc.v2022.i4.266-290
Search ePrint
Search Google
Abstract: 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.
  title={On the Lower Bound of Cost of MDS Matrices},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={2022, Issue 4},
  author={Ayineedi Venkateswarlu and Abhishek Kesarwani and Sumanta Sarkar},