TY - JOUR
AU - Venkateswarlu, Ayineedi
AU - Kesarwani, Abhishek
AU - Sarkar, Sumanta
PY - 2022/12/07
Y2 - 2023/02/07
TI - On the Lower Bound of Cost of MDS Matrices
JF - IACR Transactions on Symmetric Cryptology
JA - ToSC
VL - 2022
IS - 4
SE - Articles
DO - 10.46586/tosc.v2022.i4.266-290
UR - https://tosc.iacr.org/index.php/ToSC/article/view/9979
SP - 266-290
AB - <p>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 <em>d</em>-XOR, <em>s</em>-XOR and <em>g</em>-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 <em>GL</em>(<em>n</em>, F<sub><em>2</em></sub>) under the recently proposed metric <em>sequential XOR count based on words</em> (<em>sw</em>-XOR). We prove that the <em>sw</em>-XOR of such matrices is at least 8<em>n </em>+ 3, and the bound is tight as matrices with <em>sw</em>-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 <em>s</em>-XOR and<em> g</em>-XOR metrics.</p>
ER -