NDLI: On the direct construction of recursive MDS matrices

Content Provider	Springer Nature Link
Author	Venkateswarlu, Ayineedi Pandey, Sumit Kumar Gupta, Kishan Chand
Copyright Year	2016
Abstract	MDS matrices allow to build optimal linear diffusion layers in the design of block ciphers and hash functions. There has been a lot of study in designing efficient MDS matrices suitable for software and/or hardware implementations. In particular recursive MDS matrices are considered for resource constrained environments. Such matrices can be expressed as a power of simple companion matrices, i.e., an MDS matrix $$M = C_g^k$$ for some companion matrix corresponding to a monic polynomial $$g(X) \in \mathbb {F}_q[X]$$ of degree k. In this paper, we first show that for a monic polynomial g(X) of degree $$k\ge 2$$ , the matrix $$M = C_g^k$$ is MDS if and only if g(X) has no nonzero multiple of degree $$\le 2k-1$$ and weight $$\le k$$ . This characterization answers the issues raised by Augot et al. in FSE-2014 paper to some extent. We then revisit the algorithm given by Augot et al. to find all recursive MDS matrices that can be obtained from a class of BCH codes (which are also MDS) and propose an improved algorithm. We identify exactly what candidates in this class of BCH codes yield recursive MDS matrices. So the computation can be confined to only those potential candidate polynomials, and thus greatly reducing the complexity. As a consequence we are able to provide formulae for the number of such recursive MDS matrices, whereas in FSE-2014 paper, the same numbers are provided by exhaustively searching for some small parameter choices. We also present a few ideas making the search faster for finding efficient recursive MDS matrices in this class. Using our approach, it is possible to exhaustively search this class for larger parameter choices which was not possible earlier. We also present our search results for the case $$k=8$$ and $$q=2^{16}$$ .
Ending Page	94
Page Count	18
Starting Page	77
File Format	PDF
ISSN	09251022
e-ISSN	15737586
Journal	Designs, Codes and Cryptography
Issue Number	1-2
Volume Number	82
Language	English
Publisher	Springer US
Publisher Date	2016-06-14
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Companion matrices Cyclic Codes Information and Communication, Circuits Data Encryption Algebraic coding theory; cryptography Diffusion layer MDS codes Applications to coding theory and cryptography Data Structures, Cryptology and Information Theory Discrete Mathematics in Computer Science Coding and Information Theory Shortened Codes BCH codes Cryptography Combinatorics Cyclic codes Recursive MDS matrices
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Discrete Mathematics and Combinatorics Theoretical Computer Science Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Towards a general construction of recursive MDS diffusion layers

On the Direct Construction of Recursive MDS Matrices

On the Direct Construction of Recursive MDS Matrices

Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes

On construction of involutory MDS matrices from Vandermonde Matrices in GF(2 q )

Quaternary 1-generator quasi-cyclic codes

New MDS self-dual codes over finite fields

New binary codes from extended Goppa codes

Kernels and ranks of cyclic and negacyclic quaternary codes

On the direct construction of recursive MDS matrices

Similar Documents

Towards a general construction of recursive MDS diffusion layers

On the Direct Construction of Recursive MDS Matrices

On the Direct Construction of Recursive MDS Matrices

Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes

On construction of involutory MDS matrices from Vandermonde Matrices in GF(2 q )

Quaternary 1-generator quasi-cyclic codes

New MDS self-dual codes over finite fields

New binary codes from extended Goppa codes

Kernels and ranks of cyclic and negacyclic quaternary codes

On the direct construction of recursive MDS matrices