Paper 2026/1973

Addition-Efficient MDS Matrices from Superconcentrators (Full Version)

Abstract

MDS matrices are a key structure for providing optimal diffusion in symmetric primitives. However, the theoretical analysis of their cost remains limited. This issue is particularly relevant to arithmetization-oriented permutations, where designs often either use costly MDS matrices or sacrifice the MDS property to reduce the number of constraints. This paper studies the number of fan-in-two additions needed to implement MDS matrices. We represent fan-in-two addition constraints by a directed acyclic graph and derive lower bounds on the number of additions using the established result that any such computation graph implementing an MDS matrix must be a superconcentrator. Building on size-reduction lemmas for superconcentrators, we present a recursive algorithm that improves both lower and upper bounds for $t\times t$ matrices with $t\leq 8$. As a result, we obtain explicit MDS matrices over large primes for $t=3,4,5,6,7,8$, requiring $5,8,12,16,21,26$ additions, respectively. These bounds are tight for $t\leq 6$. We also use the same superconcentrator graphs as templates for MDS matrices with $k$-bit words. For $t=5,6,7$, our matrices require fewer XORs than the state of the art for most considered parameter choices in this line of work.