pith. sign in

arxiv: 2306.12848 · v4 · submitted 2023-06-22 · 💻 cs.IT · cs.CR· math.IT

On the Direct Construction of MDS and Near-MDS Matrices

Kishan Chand Gupta , Sumit Kumar Pandey , Susanta Samanta This is my paper

Pith reviewed 2026-05-24 08:46 UTC · model grok-4.3

classification 💻 cs.IT cs.CRmath.IT
keywords MDS matricesNear-MDS matricesgeneralized Vandermonde matricesdiffusion layersblock ciphersrecursive constructionsinvolutory matrices
0
0 comments X

The pith

Generalized Vandermonde matrices over finite fields yield direct constructions of MDS and NMDS matrices in recursive and involutory forms.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper supplies direct construction methods for Near-MDS matrices in both nonrecursive and recursive settings, removing reliance on exhaustive search for larger sizes. It also supplies direct nonrecursive MDS constructions drawn from generalized Vandermonde matrices and a method to obtain involutory versions of both MDS and NMDS matrices from the same source. The work further supplies proofs for several previously unproven folklore statements about NMDS codes. These results matter to designers of block ciphers and hash functions because they make it possible to obtain diffusion layers with known branch numbers by choosing parameters rather than searching through large spaces.

Core claim

Direct constructions of NMDS matrices are given in both nonrecursive and recursive settings, direct constructions of nonrecursive MDS matrices are obtained from generalized Vandermonde matrices, a method is proposed for constructing involutory MDS and NMDS matrices using generalized Vandermonde matrices, and several folklore results used in the literature on NMDS codes are proved.

What carries the argument

Generalized Vandermonde matrices over finite fields, whose determinant and submatrix properties are used to enforce the required branch numbers.

If this is right

  • Recursive NMDS matrices become constructible directly for use in lightweight ciphers.
  • Nonrecursive MDS matrices of larger orders can be produced from generalized Vandermonde matrices without search.
  • Involutory MDS and NMDS matrices are obtainable by the same generalized Vandermonde approach.
  • Formal proofs now support several standard claims about NMDS codes that had been treated as folklore.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Parameter selection may replace search in the design workflow for diffusion layers of new primitives.
  • Recursive NMDS forms could allow smaller hardware footprints than non-recursive counterparts of equal security level.

Load-bearing premise

The algebraic properties of generalized Vandermonde matrices over finite fields are sufficient to guarantee the required branch numbers for MDS and NMDS when parameters are chosen appropriately.

What would settle it

An explicit parameter choice for which the output matrix has branch number strictly less than claimed for its size would refute the constructions.

read the original abstract

The optimal branch number of MDS matrices makes them a preferred choice for designing diffusion layers in many block ciphers and hash functions. Consequently, various methods have been proposed for designing MDS matrices, including search and direct methods. While exhaustive search is suitable for small order MDS matrices, direct constructions are preferred for larger orders due to the vast search space involved. In the literature, there has been extensive research on the direct construction of MDS matrices using both recursive and nonrecursive methods. On the other hand, in lightweight cryptography, Near-MDS (NMDS) matrices with sub-optimal branch numbers offer a better balance between security and efficiency as a diffusion layer compared to MDS matrices. However, no direct construction method is available in the literature for constructing recursive NMDS matrices. This paper introduces some direct constructions of NMDS matrices in both nonrecursive and recursive settings. Additionally, it presents some direct constructions of nonrecursive MDS matrices from the generalized Vandermonde matrices. We propose a method for constructing involutory MDS and NMDS matrices using generalized Vandermonde matrices. Furthermore, we prove some folklore results that are used in the literature related to the NMDS code.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper claims direct algebraic constructions of non-recursive and recursive NMDS matrices, non-recursive MDS matrices derived from generalized Vandermonde matrices over finite fields, and involutory variants of both MDS and NMDS matrices also based on generalized Vandermonde matrices. It additionally proves several folklore results on the properties of NMDS codes.

Significance. If the constructions are fully rigorous, they would supply explicit parameter choices for diffusion layers that avoid exhaustive search, which is valuable for lightweight block ciphers and hash functions where NMDS matrices trade a small reduction in branch number for lower implementation cost. The provision of both recursive and involutory families would be a concrete contribution to the literature on direct MDS/NMDS constructions.

major comments (3)
  1. [§4.2] §4.2, Construction 2 (recursive NMDS): the claim that the resulting matrix satisfies the NMDS distance condition rests on the generalized Vandermonde submatrices being nonsingular for the chosen field elements and orders, yet the manuscript provides no explicit verification or determinant computation for the specific recursive parameters; this is load-bearing for the branch-number guarantee.
  2. [§5] §5, Theorem 5 (involutory NMDS): the involutory property is obtained by a particular choice of parameters in the generalized Vandermonde matrix, but the proof does not derive the required minor nonsingularity conditions from first principles for the NMDS case; it invokes the same algebraic properties used for the MDS case without additional checks.
  3. [§3.1] §3.1, Lemma 1 (folklore NMDS result): the stated equivalence between the near-MDS distance and the non-vanishing of certain minors is used repeatedly in later constructions, but the lemma is proved only for the non-recursive setting; its applicability to the recursive constructions in §4 is not justified.
minor comments (2)
  1. [§2] Notation for the generalized Vandermonde matrix is introduced in §2 but the precise definition of the auxiliary polynomial parameters is repeated in each construction section; a single centralized definition would improve readability.
  2. [Table 2] Several field-element examples in Table 2 lack the explicit minimal polynomial or the order of the field; adding these would allow independent verification of the claimed matrices.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and insightful comments on our manuscript. We address each major comment point by point below, indicating revisions where they strengthen the presentation without altering the core results.

read point-by-point responses

  1. Referee: [§4.2] §4.2, Construction 2 (recursive NMDS): the claim that the resulting matrix satisfies the NMDS distance condition rests on the generalized Vandermonde submatrices being nonsingular for the chosen field elements and orders, yet the manuscript provides no explicit verification or determinant computation for the specific recursive parameters; this is load-bearing for the branch-number guarantee.

    Authors: The nonsingularity follows from the determinant formula for generalized Vandermonde matrices given in Section 2, which holds whenever the chosen field elements are distinct; Construction 2 selects precisely such elements and builds the recursive matrix from the same set, so the relevant submatrices remain generalized Vandermonde. To make the link explicit for the recursive parameters, we will insert a short clarifying remark in §4.2 that directly invokes the Section 2 determinant condition. revision: partial

  2. Referee: [§5] §5, Theorem 5 (involutory NMDS): the involutory property is obtained by a particular choice of parameters in the generalized Vandermonde matrix, but the proof does not derive the required minor nonsingularity conditions from first principles for the NMDS case; it invokes the same algebraic properties used for the MDS case without additional checks.

    Authors: Because the NMDS property requires only a subset of the minors to be nonsingular (compared with the full MDS requirement), the parameter choices that already guarantee the stronger MDS minor conditions automatically satisfy the weaker NMDS conditions; the involutory constraint is imposed separately via the same generalized Vandermonde form and does not disturb those minors. We will revise the proof of Theorem 5 to state this implication explicitly. revision: yes

  3. Referee: [§3.1] §3.1, Lemma 1 (folklore NMDS result): the stated equivalence between the near-MDS distance and the non-vanishing of certain minors is used repeatedly in later constructions, but the lemma is proved only for the non-recursive setting; its applicability to the recursive constructions in §4 is not justified.

    Authors: Lemma 1 is formulated and proved for arbitrary matrices over finite fields; the proof nowhere invokes a non-recursive structure and therefore applies verbatim to any matrix, including the recursive matrices constructed in §4. We will add one sentence in the opening paragraph of §4 that explicitly notes this generality. revision: yes

Circularity Check

0 steps flagged

No circularity: algebraic constructions from generalized Vandermonde are self-contained

full rationale

The paper presents direct constructions of MDS/NMDS matrices using generalized Vandermonde matrices over finite fields, along with proofs of folklore results on NMDS codes. No step reduces a claimed prediction or uniqueness result to a fitted parameter, self-citation chain, or definitional renaming. The branch-number guarantees are asserted via algebraic properties of the matrices (nonsingularity of submatrices), which are independent of the target claims and not shown to be equivalent to the inputs by construction. Self-citations, if present, are not load-bearing for the central derivations. This is a standard non-circular algebraic paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; the work rests on standard finite-field algebra and Vandermonde matrix properties already present in the prior literature.

pith-pipeline@v0.9.0 · 5735 in / 1151 out tokens · 26431 ms · 2026-05-24T08:46:08.224603+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [1]

    Direct Construction o f Recursive MDS Diffusion Layers Using Shortened BCH Codes

    Daniel Augot and Matthieu Finiasz. Direct Construction o f Recursive MDS Diffusion Layers Using Shortened BCH Codes. In Carlos Cid and Christian Rechberger, editors, Fast Software Encryption , pages 3–17, Berlin, Heidelberg,

    work page

  2. [2]

    Springer Berlin Heidelberg

    work page

  3. [3]

    Thierry P. Berger. Construction of Recursive MDS Diffusio n Layers from Gabidulin codes. In Goutam Paul and Serge Vaudenay, editors , Progress in Cryptology – INDOCRYPT 2013 , pages 274–285, Cham, 2013. Springer International Publishing. On the Direct Construction of MDS and Near-MDS Matrices 27

    work page 2013

  4. [4]

    The Design of Rijndael: AES - The Advanced Encryption Standard

    Joan Daemen and Vincent Rijmen. The Design of Rijndael: AES - The Advanced Encryption Standard. Information Security and Cryptography. Springer, 2002

    work page 2002

  5. [5]

    Mario A. De Boer. Almost MDS codes. Designs, Codes and Cryptography , 9(2):143–155, Oct 1996

    work page 1996

  6. [6]

    On near-MDS codes

    Stefan Dodunekov and Ivan Landgev. On near-MDS codes. Journal of Geometry , 54(1):30–43, 1995

    work page 1995

  7. [7]

    El-Mikkawy

    Moawwad E.A. El-Mikkawy. Explicit inverse of a generaliz ed Vandermonde matrix. Applied Mathematics and Computation , 146(2):643–651, 2003

    work page 2003

  8. [8]

    Spectral analysis o f families of operator polynomials and a generalized Vandermonde matrix ii: The in finite dimensional case

    I Gohberg, M.A Kaashoek, and L Rodman. Spectral analysis o f families of operator polynomials and a generalized Vandermonde matrix ii: The in finite dimensional case. Journal of Functional Analysis , 30(3):358–389, 1978

    work page 1978

  9. [9]

    The PHOTON Fa mily of Lightweight Hash Functions

    Jian Guo, Thomas Peyrin, and Axel Poschmann. The PHOTON Fa mily of Lightweight Hash Functions. In Phillip Rogaway, editor, Advances in Cryptology – CRYPTO 2011 , pages 222–239, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg

    work page 2011

  10. [10]

    The LED Block Cipher

    Jian Guo, Thomas Peyrin, Axel Poschmann, and Matt Robshaw . The LED Block Cipher. In Bart Preneel and Tsuyoshi Takagi, editors, Cryptographic Hardware and Embedded Systems – CHES 2011 , pages 326–341, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg

    work page 2011

  11. [11]

    Cryptographically significant MDS matrices over fi nite fields: A brief survey and some generalized results

    Kishan Chand Gupta, Sumit Kumar Pandey, Indranil Ghosh R ay, and Susanta Samanta. Cryptographically significant MDS matrices over fi nite fields: A brief survey and some generalized results. Advances in Mathematics of Communications , 13(4):779–843, 2019

    work page 2019

  12. [12]

    On the construction of near-MDS matrices

    Kishan Chand Gupta, Sumit Kumar Pandey, and Susanta Sama nta. On the construction of near-MDS matrices. Cryptography and Communications, Aug 2023

    work page 2023

  13. [13]

    Towards a General Construction of Recursive MDS Diffusion La yers

    Kishan Chand Gupta, Sumit Kumar Pandey, and Ayineedi Ven kateswarlu. Towards a General Construction of Recursive MDS Diffusion La yers. In Pascale Charpin, Nicolas Sendrier, and Jean-Pierre Tillich, edito rs, The 9th International Workshop on Coding and Cryptography 2015 WCC2015 , Proceedings of the 9th International Workshop on Coding and Cryptography 201...

    work page 2015

  14. [14]

    On the direct construction of recursive MDS matrices

    Kishan Chand Gupta, Sumit Kumar Pandey, and Ayineedi Ven kateswarlu. On the direct construction of recursive MDS matrices. Designs, Codes and Cryptography , 82(1-2):77–94, 2017

    work page 2017

  15. [15]

    Towards a general construction of recursive MDS diffusion la yers

    Kishan Chand Gupta, Sumit Kumar Pandey, and Ayineedi Ven kateswarlu. Towards a general construction of recursive MDS diffusion la yers. Designs, Codes and Cryptography, 82(1-2):179–195, 2017

    work page 2017

  16. [16]

    Almost involutory recursive MDS diffusion layers

    Kishan Chand Gupta, Sumit Kumar Pandey, and Ayineedi Ven kateswarlu. Almost involutory recursive MDS diffusion layers. Designs, Codes and Cryptography , 87(2- 3):609–626, 2019

    work page 2019

  17. [17]

    On Constructi ons of Involutory MDS Matrices

    Kishan Chand Gupta and Indranil Ghosh Ray. On Constructi ons of Involutory MDS Matrices. In Amr Youssef, Abderrahmane Nitaj, and Aboul Ella Hassanien, editors, Progress in Cryptology – AFRICACRYPT 2013 , pages 43–60, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg

    work page 2013

  18. [18]

    MDS or NMD S self-dual codes from twisted generalized Reed-Solomon codes

    Daitao Huang, Qin Yue, Yongfeng Niu, and Xia Li. MDS or NMD S self-dual codes from twisted generalized Reed-Solomon codes. Designs, Codes and Cryptography , 89(9):2195–2209, Sep 2021

    work page 2021

  19. [19]

    Factorization of determinants over finite fields and applica tion in stream ciphers

    Nicholas Kolokotronis, Konstantinos Limniotis, and Ni cholas Kalouptsidis. Factorization of determinants over finite fields and applica tion in stream ciphers. Cryptography and Communications , 1:175–205, 2009. 28 K. C. Gupta et al

    work page 2009

  20. [20]

    A Construction of Matrice s with No Singular Square Submatrices

    Jérôme Lacan and Jérôme Fimes. A Construction of Matrice s with No Singular Square Submatrices. In Gary L. Mullen, Alain Poli, and Henni ng Stichtenoth, editors, Finite Fields and Applications , pages 145–147, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg

    work page 2004

  21. [21]

    Systematic MDS erasure co des based on Vandermonde matrices

    Jérôme Lacan and Jérôme Fimes. Systematic MDS erasure co des based on Vandermonde matrices. IEEE Communications Letters , 8(9):570–572, 2004

    work page 2004

  22. [22]

    Design of lightweight linear diffusion layers from near-mds matrices

    Chaoyun Li and Qingju Wang. Design of lightweight linear diffusion layers from near-mds matrices. IACR Transactions on Symmetric Cryptology , 2017(1):129– 155, Mar. 2017

    work page 2017

  23. [23]

    Constructions of Iterative Ne ar-MDS Matrices with the Lowest XOR Count

    Xiaodan Li and Wenling Wu. Constructions of Iterative Ne ar-MDS Matrices with the Lowest XOR Count. In Joonsang Baek and Sushmita Ruj, edit ors, Information Security and Privacy , pages 132–150, Cham, 2021. Springer International Publishing

    work page 2021

  24. [24]

    MacWilliams and N.J.A

    F.J. MacWilliams and N.J.A. Sloane. The Theory of Error Correcting Codes . North-Holland Publishing Co., Amsterdam-New York-Oxford , 1977

    work page 1977

  25. [25]

    C omplexity comparison of the use of Vandermonde versus Hankel matrices to build sys tematic MDS Reed- Solomon codes

    Ferdaouss Mattoussi, Vincent Roca, and Bessem Sayadi. C omplexity comparison of the use of Vandermonde versus Hankel matrices to build sys tematic MDS Reed- Solomon codes. In 2012 IEEE 13th International Workshop on Signal Processing Advances in Wireless Communications (SPA WC), pages 344–348, 2012

    work page 2012

  26. [26]

    Henry M. Power. The companion matrix and Liapunov functi ons for linear multivariable time-invariant systems. Journal of the Franklin Institute , 283(3):214– 234, 1967

    work page 1967

  27. [27]

    Ramachandra Rao and P

    A. Ramachandra Rao and P. Bhimasankaram. Linear Algebra. Hindustan Book Agency, 2000

    work page 2000

  28. [28]

    On construction of Involutory MDS Matrices from Vandermonde M atrices in GF (2q)

    Mahdi Sajadieh, Mohammad Dakhilalian, Hamid Mala, and B ehnaz Omoomi. On construction of Involutory MDS Matrices from Vandermonde M atrices in GF (2q). Designs, Codes and Cryptography , 64(3):287–308, sep 2012

    work page 2012

  29. [29]

    C. P. Schnorr and S. Vaudenay. Black box cryptanalysis of hash networks based on multipermutations. In Alfredo De Santis, editor, Advances in Cryptology — EUROCRYPT’94 , pages 47–57, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg

    work page 1995

  30. [30]

    C. E. Shannon. Communication theory of secrecy systems. The Bell System Technical Journal, 28(4):656–715, 1949

    work page 1949

  31. [31]

    Shparlinski

    Igor E. Shparlinski. On the singularity of generalised V andermonde matrices over finite fields. Finite Fields and Their Applications , 11(2):193–199, 2005

    work page 2005

  32. [32]

    MDS, Near- MDS or 2-MDS Self- Dual Codes via Twisted Generalized Reed-Solomon Codes

    Junzhen Sui, Qin Yue, Xia Li, and Daitao Huang. MDS, Near- MDS or 2-MDS Self- Dual Codes via Twisted Generalized Reed-Solomon Codes. IEEE Transactions on Information Theory, 68(12):7832–7841, 2022

    work page 2022

  33. [33]

    MDS and near- MDS codes via twisted Reed–Solomon codes

    Junzhen Sui, Xiaomeng Zhu, and Xueying Shi. MDS and near- MDS codes via twisted Reed–Solomon codes. Designs, Codes and Cryptography , 90(8):1937–1958, Aug 2022

    work page 1937

  34. [34]

    Van de Vel

    H. Van de Vel. Numerical treatment of a generalized Vande rmonde system of equations. Linear Algebra and its Applications , 17(2):149–179, 1977

    work page 1977

  35. [35]

    On the need for multipermutations: Cryp tanalysis of MD4 and SAFER

    Serge Vaudenay. On the need for multipermutations: Cryp tanalysis of MD4 and SAFER. In Bart Preneel, editor, Fast Software Encryption , pages 286–297, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg

    work page 1995

  36. [36]

    V.K. Wei. Generalized hamming weights for linear codes. IEEE Transactions on Information Theory, 37(5):1412–1418, 1991

    work page 1991