Matrix code distances shift predictably under add and remove operations
Code distances of matrix rank-metric codes under Add-and-Remove transformations
Information Theory
Summary
Matrix rank-metric codes have a property called subcode distances, which measure how 'different' smaller parts of the code are. The authors study how these distances change when you keep some parts of a code and add new parts, a process important in certain digital signature systems like MIRANDA. They provide formulas and inequalities showing exactly how the subcode distances shift in these transformations, especially for a special type of code called Gabidulin codes. Their work helps understand the security and structure of codes used in cryptography.
What this means in practice
- •For cryptographic engineers: Evaluate and ensure the security properties of rank-metric codes used in signature schemes like MIRANDA when updating code components.
- •For error correction system developers: Design matrix codes with predictable distance properties after dimensional changes to improve reliability in communication systems.
Authors
Gianira N. Alfarano, Rakhi Pratihar, Adrien Vinçotte
Abstract
For a matrix rank-metric code $\mathcal{C}$ and an integer $i$, the $i$-th subcode distance of $\mathcal{C}$ is the largest minimum rank distance of an $i$-dimensional subcode of $\mathcal{C}$. We study how subcode distances change under the Add-and-Remove construction, in which a subcode of codimension $\ell_s$ is kept and a space of dimension $\ell_a$ is added; this construction is used, with Gabidulin codes, in the $\mathsf{MIRANDA}$ signature scheme. For arbitrary matrix codes, we give inequalities between the subcode distances of the original and of the new code, and we show that Delsarte duality interchanges $\ell_s$ and $\ell_a$. For matrix Gabidulin codes, whose subcode distances are given by an explicit formula, we show that, if $\ell_s<\max\{m,n\}$, then within each block of indices $(a-1)\max\{m,n\}+1,\ldots,a\max\{m,n\}$ not exceeding $\dim_{\mathbb{F}_q}(\mathcal{C}_s)$, all but the last $\ell_s$ subcode distances are the same as for the Gabidulin code, and the remaining ones decrease by at most one; a small example shows that such a decrease can occur. We also express the minimum distance of the new code in terms of the rank distance between the added space and the common subcode. For $\mathsf{MIRANDA}$, the lower bound on the minimum distance of the dual public code used by the known distinguisher when $\ell_s=0$ is a special case of these results; for the proposed parameters, where $\ell_s>0$, the same bound holds for a subcode of codimension $\ell_s$ of the dual public code.