International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On Efficient Constructions of Lightweight MDS Matrices

Authors:
Lijing Zhou , State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing
Licheng Wang , State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing
Yiru Sun , State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing
Download:
DOI: 10.13154/tosc.v2018.i1.180-200
URL: https://tosc.iacr.org/index.php/ToSC/article/view/849
Search ePrint
Search Google
Abstract: The paper investigates the maximum distance separable (MDS) matrix over the matrix polynomial residue ring. Firstly, by analyzing the minimal polynomials of binary matrices with 1 XOR count and element-matrices with few XOR counts, we present an efficient method for constructing MDS matrices with as few XOR counts as possible. Comparing with previous constructions, our corresponding constructions only cost 1 minute 27 seconds to 7 minutes, while previous constructions cost 3 days to 4 weeks. Secondly, we discuss the existence of several types of involutory MDS matrices and propose an efficient necessary-and-sufficient condition for identifying a Hadamard matrix being involutory. According to the condition, each involutory Hadamard matrix over a polynomial residue ring can be accurately and efficiently searched. Furthermore, we devise an efficient algorithm for constructing involutory Hadamard MDS matrices with as few XOR counts as possible. We obtain many new involutory Hadamard MDS matrices with much fewer XOR counts than optimal results reported before.
BibTeX
@article{tosc-2018-28394,
  title={On Efficient Constructions of Lightweight MDS Matrices},
  journal={IACR Trans. Symmetric Cryptol.},
  publisher={Ruhr-Universität Bochum},
  volume={2018, Issue 1},
  pages={180-200},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/849},
  doi={10.13154/tosc.v2018.i1.180-200},
  author={Lijing Zhou and Licheng Wang and Yiru Sun},
  year=2018
}