Paper 2023/1521

A reduced set of submatrices for a faster evaluation of the MDS property of a circulant matrix with entries that are powers of two

Dragan Lambić, Ponos Technology (Switzerland), University of Novi Sad, Faculty of Education, Sombor (Serbia)
Abstract

In this paper a reduced set of submatrices for a faster evaluation of the MDS property of a circulant matrix, with entries that are powers of two, is proposed. A proposition is made that under the condition that all entries of a t × t circulant matrix are powers of 2, it is sufficient to check only its 2x2 submatrices in order to evaluate the MDS property in a prime field. Although there is no theoretical proof to support this proposition at this point, the experimental results conducted on a sample of 100 thousand randomly generated matrices indicate that this proposition is true. There are benefits of the proposed MDS test on the efficiency of search methods for the generation of circulant MDS matrices, regardless of the correctness of this proposition. However, if this proposition is correct, its impact on the speed of search methods for circulant MDS matrices will be huge, which will enable generation of MDS matrices of large sizes. Also, a modified version of the make_binary_powers function is presented. Based on this modified function and the proposed MDS test, some examples of efficient 16 x 16 MDS matrices are presented. Also, an examples of efficient 24 x 24 matrices are generated, whose MDS property should be further validated.

Note: In the revised manuscript, new examples of MDS matrices are added because some of the examples in the previous version of this paper were not MDS due to bug in the code used to evaluate their MDS property.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
MDS matrixHash functionsZero knowledge
Contact author(s)
dragan lambic @ pef uns ac rs
History
2023-10-11: revised
2023-10-05: received
See all versions
Short URL
https://ia.cr/2023/1521
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1521,
      author = {Dragan Lambić},
      title = {A reduced set of submatrices for a faster evaluation of the {MDS} property of a circulant matrix with entries that are powers of two},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1521},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1521}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.