PaperlayerView exact revision on arXiv

Source-linked AI summary

How to break the Miranda signature scheme over matrix Gabidulin codes

Adrien Vinçotte

arXiv:2609.30925v2cs.CR

TL;DR

Miranda masks an expanded Gabidulin code to conceal its Fqm-linearity, while structural attacks seek to recover that structure. This paper reduces Miranda key recovery in polynomial time to rank-1 MinRank. The attack reports substantially lower complexity than the scheme’s claimed security for proposed parameters.

  • Problem

    Miranda’s AddRemove masking is intended to hide the Fqm-linearity of an expanded Gabidulin code, but recovering that structure can reveal its decoding trapdoor.

    Source: §2.4 · pp. 8–9

  • Method

    The attack punctures the public code until its dual has dimension one over Fqm, then reduces in polynomial time to finding a rank-1 matrix with MinRank.

    Source: Contributions · p. 3, §3 · p. 9

  • Results

    The attack has complexity below 100 bits for parameters claimed at 143 bits, and 62 bits for those with the smallest m.

    Source: Contributions · p. 3

  • Takeaways & Limitations

    The attack significantly impacts the security of the proposed Miranda parameters, exploiting traces of the underlying Fqm-linearity left by AddRemove.

    Source: Contributions · p. 3

    The MinRank instance is nonrandom because its matrices have Fq coefficients, so generic solver behavior is harder to predict; the reduction also assumes ℓa < n−κ.

    Source: §3 · p. 9, §3.1 · p. 11

Abstract

from arXiv · show

The Miranda signature scheme relies on masking a matrix code which disposes of a masked underlying structure, and the knowledge of which allows for efficient error decoding. We consider a Gabidulin code which is expanded into a matrix code, that is only \Fq-linear. An additional masking is then applied to it. The attack proposed here shares similarities with that of [Le26, https://arxiv.org/abs/2608.03328] on the EGMC encryption scheme, which also follows the paradigm described above. It consists in recovering the Fqm-linear structure of a masked matrix Gabidulin code by reducing to a MinRank instance to be solved over the extension field Fqm, but where the matrices have coefficients in Fq. Such an instance can be efficiently solved. However, unlike the previous attack, it is possible to reduce in polynomial time to such a MinRank instance in the case of the Miranda signature scheme. This results in a particularly efficient key recovery attack against the parameters proposed for Miranda. For example, for the proposed parameter set with m=79, the complexity drops from 146 bits to 46 bits in this attack.

1 Introduction

The rank metric measures matrix distance by the rank of the difference, and Gabidulin codes extend this metric to vectors over Fqm. Their Fqm-linearity supports compact code representations but also creates algebraic structure that can be exploited by attacks.

1 Introduction

  • The distance between matrices A and B is rank(A−B), making rank the weight of a matrix.Gabidulin codes extend rank metric to vectors over Fqm, where vector weight is the dimension of the Fq-span of the coordinates.Source: The Two Notions of Rank Metric Codes · p. 1
  • Fqm-linearity gives Gabidulin codes a compact representation, but their algebraic rigidity enables structural attacks such as Overbeck’s recovery of masked codes [Ove08].Source: The Two Notions of Rank Metric Codes · pp. 1–2

Two Protocols Based on a Masked Fqm-Linear Matrix Code.

The paper contrasts two protocols built from masked matrix Gabidulin codes, then introduces a Miranda key-recovery attack that reduces in polynomial time to rank-1 MinRank. The attack lowers the claimed security of proposed parameters.

Two Protocols Based on a Masked Fqm-Linear Matrix Code.

  • EGMC converts Gabidulin vectors into Fq-linear matrix codes and masks them using random row and column additions propagated through invertible matrices P and Q.The resulting codes underpin EGMC-McEliece and EGMC-Niederreiter; an earlier structural attack required parameter revision [PWL26].Source: Two Protocols Based on a Masked… · p. 2
  • Miranda uses AddRemove to retain a codimension-ℓs subcode and add ℓa random matrices; its public code has ℓa > ℓs and permits decoding any element of the space.The scheme follows the GPV paradigm [GPV08], with short signatures but signing time exponential in ℓs and the Gabidulin decoding capacity.Source: Two Protocols Based on a Masked… · p. 2

Contributions.

  • Le’s EGMC attack guesses one masking matrix and derives the other from traces of the underlying Fqm-linearity, recovering an equivalent secret key [Le26].The Miranda attack adapts the structural-attack idea, but puncturing is immediate because no secret matrix interferes; the AddRemove mask leaves traces enabling a rank-1 MinRank reduction.Source: Two Protocols Based on a Masked… · pp. 2–3, Contributions · p. 3
  • The attack reduces in polynomial time to rank-1 MinRank; reported complexity is below 100 bits for parameters claimed at 143 bits, and 62 bits for the smallest m.The authors describe this as the first proposed attack against Miranda.Source: Contributions · p. 3

2 Preliminaries

The preliminaries establish how rank-metric vector codes become matrix codes, define the associated dual and MinRank problems, and introduce Gabidulin codes and Miranda’s masking construction.

2.1 Rank metric codes

  • Expanding an Fqm-linear vector code in a basis γ produces an Fq-linear matrix code; changing basis yields left-equivalent codes.Unfold writes a matrix as a vector by concatenating its rows.Source: §2 · p. 3, §2.1 · pp. 4–5

2.2 MinRank problem

  • MinRank models decoding a noisy matrix-code word: find a low-rank error consistent with the codeword or syndrome.The matrix-code decoding problem is MinRank, with the error rank as the target rank.Source: §2.2 · p. 6

Dual of a matrix code.

2.3 Gabidulin codes

  • Gabidulin codes are Fqm-linear rank-metric vector codes defined through q-polynomial evaluations and admit efficient decoding.Their strong structure is difficult to hide, while their matrix-code duals remain matrix Gabidulin codes expanded in the dual basis.Source: §2.3 · p. 7

2.4 The Miranda signature scheme

  • Miranda expands a secret Gabidulin code into a matrix code, then uses AddRemove to mask it; knowledge of the underlying expanded code is the decoding trapdoor.AddRemove combines a codimension-ℓs subcode with an ℓa-dimensional code intersecting it only at zero.Source: §2.4 · pp. 8–9

3 Key recovery attack for Miranda

The attack recovers the hidden Fqm-linear structure by reducing key recovery to a rank-1 MinRank problem. It adapts the reduction to Miranda’s masking and the resulting non-generic instance.

3 Key recovery attack for Miranda

  • Miranda’s masking leaves enough Fqm-linearity traces for the reduction, and unlike the EGMC attack, no secret matrix interferes with puncturing the public code.The reduction punctures until the code’s dual has dimension 1 over Fqm.Source: §3 · p. 9
  • The reduction assumes Fqm(Amat) has dimension ℓa, which occurs with high probability; otherwise, ℓa can be decreased until it matches the dimension of Amat.It also assumes ℓa < n − κ.Source: §3 · p. 9

3.1 Reduction in polynomial time to an easy MinRank instance

  • The recovered basis need not be unique: possible bases can lie in different equivalence classes, while the subcode Cs preserves the underlying Fqm-linearity.Source: §3.1 · p. 10
  • The attack reduces recovery of the secret Fqm basis, up to scalar, to a rank-1 MinRank instance in polynomial time.The instance has code parameters [m × (κ + ℓa + 1), ρ]qm.Source: §3.1 · pp. 9, 11
  • The MinRank instance is non-generic because its basis matrices have coefficients in Fq, so usual solvers are not necessarily accurate.Its solutions are stable under Fqm scalars and Frobenius composition.Source: §3.1 · p. 11

3.2 Solving the MinRank instance

The MinRank instance is not generic because its matrices have coefficients in Fq, making generic solver behavior harder to predict. The attack instead solves it efficiently using linear algebra over Fq, while accounting for parasitic solutions.

3.2 Solving the MinRank instance

  • The instance is non-generic because its basis matrices have coefficients in Fq, making generic solver behavior harder to predict.Source: §3.2 · p. 11
  • Linear algebra over Fq provides an efficient way to solve the MinRank system.Source: §3.2 · p. 12
  • Unlike Le’s attack [Le26], this approach encounters parasitic solutions that require additional care in the analysis.Source: §3.2 · p. 12

Step 1: modeling using minors.

The solver models rank 1 through quadratic equations from matrix minors, then solves the resulting system through its quotient algebra. The method handles multiple solution orbits and performs the algebraic computations over Fq.

Step 1: modeling using minors.

  • The target rank-1 condition is modeled by a homogeneous quadratic system formed from the 2 × 2 minors of E.The equations generate an ideal, and degree 2 is sufficient for most parameter sets while degree 3 suffices for all attacked sets.Source: Step 1: modeling using minors · p. 12
  • The solution orbit is not unique, unlike the orbit structure assumed in Le’s attack [Le26], so the adapted conjecture accounts for this difference.Source: Step 1: modeling using minors · p. 12
  • Frobenius-stable solutions need not occur in counts divisible by m; solutions over Fq are rejected because their extracted γ cannot belong to B(Fqm).Source: Step 1: modeling using minors · pp. 12–13

Step 2: solving the quadratic system.

  • If the coefficient of B1 in a MinRank solution is zero, the attack fails with probability 1/qm; specializing another variable to 1 permits a retry.Source: Step 2: solving the quadratic system · p. 13
  • Specializing x1 to 1 makes the variety discrete, allowing the Eigenvalue Theorem to recover its points using linear algebra over Fq.A random linear combination of multiplication maps is used to increase the chance of simple eigenvalues.Source: Step 2: solving the quadratic system · pp. 13–14

Step 3: extract a possible basis.

For each of the Km possible solutions, the attack unfolds E = γT h and extracts a basis vector γ, determined up to a nonzero scalar.

Step 3: extract a possible basis.

About the number of unwanted solutions.

The analysis bounds unwanted MinRank solutions and finds that their practical number is far below the upper bound. The attack recovers the secret masked code by testing candidate bases, with Gaussian elimination on the Macaulay matrix as its dominant computation.

About the number of unwanted solutions.

  • At fixed m, the kernel dimension appears independent of the public key and unaffected by κ or ℓs.The reported independence from κ and ℓs is qualified as an experimental observation.Source: About the number of unwanted solutions · p. 15

3.3 Recovering the secret masked code

  • Candidate solutions yield possible secret bases γ; guessing one allows recovery of the secret Gabidulin code after recovering Fqm-linearity.The algorithm computes a dual basis and left-stabilizer algebra, then obtains a subcode of the secret Gabidulin code and recovers the code with Overbeck-like techniques in polynomial time [Ove08].Source: §3.3 · pp. 15–16

3.4 Complexity of the attack

  • All attack computations are polynomial-time, and Gaussian elimination on the Macaulay matrix dominates the cost.The kernel computation and Overbeck-like recovery are negligible compared with simplifying the ideal; d is the smallest value for which equations outnumber unknowns.Source: §3.4 · p. 16

4 Concrete application to Miranda Parameters

For Miranda signatures, the attack applies to the dual public code, recovering the dual of the secret basis and producing complexity estimates. For the encryption scheme, attacking the original code rather than its public dual yields smaller MinRank parameters.

Signature scheme.

  • For signatures, the public code is the dual of AddRemove(Mγ(G), ℓa, ℓs), so the attack targets AddRemove(Mγ*(G⊥), ℓs, ℓa) and recovers the dual secret basis.The resulting bilinear system has a stated number of distinct monomials after specializing x1 to 1, with ρ = (m − 1)(ℓs + 1) + ℓa + 1.Source: Signature scheme · p. 16
  • The signature-parameter complexities are reported in Table 2, with “Forge” denoting direct MinRank solving and “Struct.” the structural attack.The table uses ω = 2.8 as the linear-algebra complexity exponent.Source: Signature scheme · p. 16, Table 2 · p. 17

Encryption scheme.

  • Miranda’s encryption scheme uses a decoding distance with unique solutions, choosing large ℓs and small ℓa; the authors suggest ℓa = 0.The public code is then a subcode of Mγ(G), and the ciphertext is the syndrome of a hashed matrix of rank at most t.Source: Encryption scheme · p. 17
  • For encryption with ℓa = 0, attacking AddRemove(Mγ(G), ℓs, 0) instead of its public dual gives smaller MinRank parameters.The paper reports the resulting complexities in Table 3.Source: Encryption scheme · p. 17

A Key generation of the Miranda signature scheme

The key-generation algorithm takes scheme parameters and outputs a public code together with a trapdoor containing the masked Gabidulin structure. Its stated construction includes bases for masked-code spaces and their duals.

A Key generation of the Miranda signature scheme

  • KeyGen takes the scheme parameters and outputs the public code and a trapdoor containing the Fqm-linearity structure and masked Gabidulin code.The listed parameters are q, m, n, κ, ℓa, and ℓs, selected to ensure λ bits of security.Source: A Key generation of the Miranda… · p. 20
  • The algorithm chooses a random Fq-code U of dimension ℓa disjoint from C, as shown in its construction.The displayed condition is U ∩ C = {0}.Source: A Key generation of the Miranda… · p. 20
  • KeyGen forms a random Fq-basis of (Cs ⊕ Amat)⊥, then completes it to a basis of Cs⊥.The listed basis sizes are (n−κ)m+ℓs−ℓa and mn−κm+ℓs, respectively.Source: A Key generation of the Miranda… · p. 20

B Inversion of the Miranda trapdoor [CDAGV25]

Signing samples a candidate matrix and attempts to decode its expanded representation in the secret Gabidulin code. It maps a decoded error back to a matrix and checks membership in the secret subcode, retrying when decoding or verification fails.

B Inversion of the Miranda trapdoor [CDAGV25]

  • The signing procedure uses a basis of AddRemove(Gκ(g), ℓa, ℓs), samples t in Fq^ℓa, and computes a matrix Y by linear algebra.The basis includes the specified Bi elements and ℓa additional matrices from the trapdoor.Source: B Inversion of the Miranda trapdoor… · pp. 20–21
  • It expands Y and tries to decode y in Gκ(g); if decoding succeeds, the decoded e has rank at most t and is mapped to E.The expansion is an isometry, so E also has rank at most t.Source: B Inversion of the Miranda trapdoor… · p. 21
  • The algorithm verifies that Y − E lies in Cs and retries with another t if decoding fails or the membership check does not hold.Successful verification completes the signing procedure.Source: B Inversion of the Miranda trapdoor… · p. 21
Loading 2609.30925v2…