PaperlayerView exact revision on arXiv

Source-linked AI summary

Code distances of matrix rank-metric codes under Add-and-Remove transformations

Gianira N. Alfarano, Rakhi Pratihar, Adrien Vinçotte

arXiv:2610.03460v1cs.ITmath.IT

TL;DR

The paper asks which subcode distances survive the Add-and-Remove construction used with Gabidulin codes in MIRANDA. It derives general bounds and duality relations, then shows that most Gabidulin subcode distances are preserved under a condition on ℓs.

  • Problem

    Minimum distance alone does not reveal how much structure an Add-and-Remove code retains, while subcode distances can distinguish some inequivalent MRD codes with the same parameters.

    Source: §1 · p. 2

  • Method

    The paper bounds subcode distances for Add-and-Remove codes, analyzes Gabidulin codes using their subcode-distance formula, and applies the bounds to MIRANDA’s dual public code.

    Source: §1 · p. 2, §5 · p. 7

  • Results

    For ℓs < max{m, n}, only the last ℓs indices in each specified block can differ from Gabidulin subcode distances, and any decrease is at most one.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For MIRANDA with ℓs > 0, the known distinguisher’s lower bound on dual-public-code minimum distance also holds for a subcode of codimension ℓs.

    Source: §6 · p. 9

    Whether exceptional-index decreases occur often, especially for MIRANDA parameters, and whether subcode distances enable a polynomial-time distinguisher remain open.

    Source: §1 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

The paper studies how subcode distances reveal structure retained by Add-and-Remove codes, a construction used in the MIRANDA signature scheme. It establishes preservation results and identifies open questions about their reach.

Contributions

  • For arbitrary matrix codes, the paper bounds how subcode distances change under Add-and-Remove and shows duality interchanges the removal and addition parameters.For Gabidulin codes, most subcode distances are preserved under the stated condition; the exceptions can decrease by at most one.Source: §1 · p. 2
  • When ℓs < max{m, n}, only the last ℓs indices in each specified block can differ from the Gabidulin code, and each decreases by at most one.The paper reports an example where a decrease occurs.Source: §1 · p. 2
  • The minimum distance of the constructed code depends on the added space’s position relative to the retained subcode, and the paper characterizes when the result is MRD.When the retained subcode is one dimension short of a Gabidulin code, the resulting subcode distances up to its dimension attain the Singleton bound.Source: §1 · p. 2
  • For MIRANDA, the known distinguisher’s dual-public-code minimum-distance bound extends to a subcode of codimension ℓs when ℓs > 0.Using other subcode distances in a distinguisher remains future work.Source: §1 · p. 2

Open questions

  • Whether exceptional-index decreases occur often, especially for MIRANDA parameters, and whether subcode distances enable a polynomial-time distinguisher remain open.The latter question requires knowing subcode distances of random matrix codes.Source: §1 · p. 2

2 Preliminaries

The preliminaries define matrix rank-metric codes and their distances, relate vector and matrix representations, and introduce Add-and-Remove codes and subcode distances. They also give the subcode-distance formula used for Gabidulin codes.

2 Preliminaries

  • The preliminaries set q as a prime power, define μ = max{m, n} and ν = min{m, n}, and take matrix codes over Fq.The standard trace inner product defines the dual code, whose dimension is mn minus the original code’s dimension.Source: §2 · p. 2, §2.1 · p. 3

2.1 Matrix rank-metric codes

  • A matrix rank-metric code is an Fq-linear subspace of matrices, with rank distance determined by the rank of the matrix difference and minimum distance equal to its least nonzero rank.The Singleton-like bound constrains dimension and minimum distance; equality defines an MRD code.Source: §2.1 · p. 3

2.2 Vector rank metric, matrix expansion, and Gabidulin codes

  • Vector rank-metric codes over Fq^μ expand through a basis into matrices, preserving rank distance; Gabidulin codes yield MRD matrix codes under this expansion.The nested Gabidulin subcodes have dimensions m times their index.Source: §2.2 · p. 3

2.3 Add-and-Remove construction

  • Add-and-Remove forms D = Cs ⊕ A by retaining a codimension-ℓs subcode and adding an ℓa-dimensional space disjoint from C.The common subcode is C ∩ D, so the two parameters are determined by the pair of codes.Source: §2.3 · pp. 3–4

2.4 Subcode distances

  • The i-th subcode distance is the greatest minimum distance among i-dimensional subcodes, and its values are bounded by the Singleton estimate.For matrix Gabidulin codes, equality holds for every index, with the formula established using the nested subcodes.Source: §2.4 · p. 4

3 Subcode Distances under Add-and-Remove

The section derives general inequalities for subcode distances under Add-and-Remove and shows how duality transforms the construction. Under a plateau condition, the bounds force exact preservation.

3 Subcode Distances under Add-and-Remove

  • For arbitrary matrix codes, the paper gives inequalities relating the subcode distances of C, its retained subcode Cs, and the constructed code D.These bounds use the inclusions and the codimensions ℓs and ℓa.Source: §3 · p. 4
  • D⊥ is an Add-and-Remove transform of C⊥ with ℓs and ℓa interchanged.The common subcode in the dual construction has codimension ℓa in C⊥ and ℓs in D⊥.Source: §3 · p. 5
  • If the original code’s subcode distances are equal across the specified index interval, the corresponding subcode distance of D equals that common value.The result follows by squeezing the distance between the general lower and upper bounds.Source: §3 · p. 5

4 Add-and-Remove Gabidulin Codes

For a Gabidulin code C, this section studies D = Cs ⊕ A, where Cs is a subcode and A is an added space disjoint from C, deriving bounds on subcode distances and results for minimum distance.

4.1 General bounds

  • For i ≤ dimFq(Cs), the bounds on α_i(D) differ by at most one when ℓ_s ≤ m; if ℓ_s < m, only the last ℓ_s indices in each m-index block can differ from C.For indices beyond dimFq(Cs), Theorem 8 does not apply, and α_i(D) can be much smaller.Source: §4.1 · pp. 5–6
  • For i = (a−1)m+t ≤ mκ−ℓ_s, α_i(D) = n−a+1 when t ≤ m−ℓ_s; in the remaining ℓ_s positions, it is n−a+1 or n−a, and both values occur.When ℓ_s = 0, α_i(D) = n−⌈i/m⌉+1 throughout the code.Source: §4.1 · p. 6

4.2 The minimum distance

  • D’s minimum distance depends on A, and an Add-and-Remove operation need not preserve the MRD property.When ℓ_a = ℓ_s, D has dimension mκ and is MRD exactly under the criterion stated in the section.Source: §4.2 · p. 6

4.3 Removing one Fqm-dimension

  • When C0 is the specified Gabidulin subcode and dim A = m with A ∩ C = {0}, every α_i(D) for i ≤ m(κ−1) attains the Singleton bound, and D is MRD iff Δ(A,C0) = n−κ+1.For these parameters, d(D) = min{n−κ+2, Δ(A,C0)}.Source: §4.3 · pp. 6–7

5 Application to MIRANDA and an Example

For MIRANDA’s Gabidulin-based construction, the paper applies its subcode-distance bounds to the public code and its dual, then illustrates when exceptional distances can decrease. The examples and comparison with random codes also identify what the results do and do not establish.

Application to MIRANDA

  • For the illustrated MIRANDA parameters, (m,n,κ,ℓ_a,ℓ_s)=(113,113,107,220,3), with dim_Fq(C_s)=12088 and dim_Fq(Dmat)=12308.The parameters are reported as targeting 128-bit security (NIST security level I).Source: §5 · p. 7
  • For the illustrated parameters, α_i(Dmat)=114−⌈i/113⌉ for i≤12088 when t≤110, and at most ℓ_s≤5 distances in any 113-index block are otherwise undetermined.Here i=(a−1)m+t, with 1≤t≤m; each C_a∩C_s also gives a subcode meeting the Singleton bound.Source: §5 · p. 7
  • When ℓ_s=0, D⊥mat contains no nonzero matrix of rank at most κ, the property used by MIRANDA’s exponential-time distinguisher; for ℓ_s>0, the guarantee applies to a codimension-ℓ_s subcode.The dual construction is a subcode of C⊥ of codimension ℓ_a, with a complementary space of dimension ℓ_s.Source: §5 · pp. 7–8
  • For the illustrated parameters, α_i(Dmat)≥114−⌈(i+3)/113⌉ for i≤12088, while same-dimension random codes satisfy α_i(U)≥114−⌈(i+461)/113⌉; whether they fall below Dmat’s bound is unknown.The paper says subcode distances could distinguish Dmat only if a random code falls below that bound with high probability.Source: §5 · p. 8
  • The second-moment argument bounds the probability that a random code contains a nonzero matrix of rank at most κ, but does not decide whether it has a codimension-ℓ_s subcode avoiding such matrices.The union bound over those subcodes is too large for the parameters considered.Source: §5 · p. 8

Example

  • In the 3×3 example, the distance sequence changes from (3,3,3,2,2,2) to (3,3,2,2,2,1), attaining the permitted decrease at index 3.A different hyperplane has α_3=2, and adding E_11 gives the sequence (3,3,2,2,2,1).Source: §5 · pp. 8–9

6 Conclusion

The conclusion summarizes the bounds for Gabidulin codes and their application to MIRANDA. It also leaves the use of other subcode distances in a distinguisher as future work.

Conclusion

  • For Gabidulin C with ℓ_s<m, α_i(D) matches α_i(C) except at the last ℓ_s indices in each length-m block, where it can decrease by one.Example 13 shows that a decrease can occur.Source: §6 · p. 9
  • For MIRANDA, the dual-public-code minimum-distance bound used by the known distinguisher extends to a codimension-ℓ_s subcode when ℓ_s>0.The known distinguisher is described for ℓ_s=0.Source: §6 · p. 9
  • Using other subcode distances in a distinguisher remains future work.The conclusion does not claim that these distances yield a new distinguisher.Source: §6 · p. 9

Declaration on the use of AI

The authors report using GPT-5.6 Luna for text refinement, calculation checks, and literature finding, while stating that no mathematical ideas were AI-generated and that they independently verified the theorem statements and proofs.

Declaration on the use of AI

  • The authors used GPT-5.6 Luna for text refinement, calculation checks, and literature finding, and report independently verifying theorem statements and proofs.They state that no mathematical ideas were generated by AI and take responsibility for the final content.Source: Declaration on the use of AI · p. 9
Loading 2610.03460v1…