On the Construction of Toeplitz MDS Matrices without Related Differentials

Abstract

MDS matrices are widely used in the linear layers of block ciphers. The concept of related differentials for linear layers was introduced by Daemen and Rijmen and later successfully applied to cryptanalysis of the AES. Consequently, the construction of MDS matrices immune to related differentials has attracted significant attention. This paper focuses on Toeplitz MDS matrices and investigates their related-differential properties. To this end, we first analyze structural properties of Toeplitz MDS matrices. Then, based on the definition of related differentials and the inherent properties of MDS matrices, we explore the relationship between the Hamming weight of matrix inputs and their corresponding outputs. Finally, we investigate the construction of Toeplitz MDS matrices free from related differentials, as well as such matrices achieving the minimum XOR count, using our proposed search frameworks. Our results demonstrate that all 3×3 and 4×4 Toeplitz MDS matrices over {\mathbb{F}}_{2^4} possess related differentials. Furthermore, we show that the 4×4 Toeplitz MDS matrices over {\mathbb{F}}_{2^8} with the minimum XOR count originally presented at ToSC 2016 also exhibit related differentials. In addition, we determine the minimum XOR count of 4×4 Toeplitz MDS matrices free from related differentials over {\mathbb{F}}_{2^5} and {\mathbb{F}}_{2^8} .

Keywords

Linear Layer / MDS / Toeplitz / Related Differentials / XOR Count

Rights & permissions

Higher Education Press 2026

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.