Loidreau's 2017 rank-metric public-key encryption scheme masks a Gabidulin code with an invertible matrix whose entries lie in a secret λ\lambda-dimensional Fq\mathbb{F}_q-subspace of Fqm\mathbb{F}_{q^m}. When the public code is distinguishable from a random code (public rate above roughly 1−1/λ1-1/\lambda), the Coggia-Couvreur attack line reduces recovering an equivalent secret key to finding one root of an explicit system of λ−1\lambda-1 multivariate polynomials over Fqm\mathbb{F}_{q^m} of degrees qλ+1−qiq^{\lambda+1}-q^i, whose root set is, under genericity hypotheses, a single orbit of the projective linear group PGL(λ,Fq)\mathrm{PGL}(\lambda,\mathbb{F}_q). Key recovery is polynomial time for masking dimensions λ≤3\lambda \le 3 (linear algebra and resultants), but for each fixed λ≥4\lambda \ge 4 no polynomial-time method, deterministic or probabilistic, is known for the root-finding step, and the genericity conditions on which the reduction rests are unproven for cryptographic parameters. This record asks for the completion, or a conclusive delimitation, of this algebraic attack: a polynomial-time root-finding algorithm or an alternative polynomial-time reduction for fixed λ≥4\lambda \ge 4, together with, as the source's explicitly stated future work, an extension of key recovery to public-code rates below 1−1/λ1-1/\lambda, where the best published attacks (Briaud-Loidreau, 2023) remain exponential.

Background

Rank-metric code-based cryptography pursues McEliece-type public-key encryption with far smaller keys than Hamming-metric schemes. The standard setting uses Fqm\mathbb{F}_{q^m}-linear codes of length nn over the extension field Fqm\mathbb{F}_{q^m}: the rank of a vector is the dimension, over the base field Fq\mathbb{F}_q, of the span of its coordinates, and the rank distance between two vectors is the rank of their difference. Gabidulin codes are the rank-metric analogues of Reed-Solomon codes: they are obtained by evaluating linearized polynomials (polynomials of the form f(X)=∑ifiXqif(X)=\sum_i f_i X^{q^i}, whose monomials are powers of the Frobenius automorphism x↦xqx \mapsto x^q) on coordinates of full rank, are maximum-rank-distance codes, and admit polynomial-time decoding up to ⌊(n−k)/2⌋\lfloor (n-k)/2 \rfloor rank errors, where kk is the code dimension.

Encryption schemes built on Gabidulin codes, starting from the GPT cryptosystem (the original Gabidulin-code-based McEliece-type proposal of 1991), mask the secret generator matrix; but the Frobenius action that defines these codes leaks structure, and a line of structural attacks culminating in Overbeck's polynomial-time attack (Journal of Cryptology, 2007) broke the early proposals by recovering the hidden code from Frobenius spans of the public code. Loidreau's 2017 scheme revived the approach with a rank multiplier: the public key is Gpub=GP−1\boldsymbol{G}_{\mathrm{pub}} = \boldsymbol{G}\boldsymbol{P}^{-1}, where G\boldsymbol{G} generates a Gabidulin code Gk(g)⊂Fqmn\mathcal{G}_k(\boldsymbol{g}) \subset \mathbb{F}_{q^m}^n and P∈GLn(Fqm)\boldsymbol{P} \in \mathrm{GL}_n(\mathbb{F}_{q^m}) has all entries in a secret λ\lambda-dimensional Fq\mathbb{F}_q-subspace V⊂Fqm\mathcal{V} \subset \mathbb{F}_{q^m} (the masking space; proposed instantiations use small λ\lambda such as 2 or 3). Multiplication by such a matrix multiplies rank weights by at most λ\lambda, so the legitimate receiver multiplies a ciphertext by P\boldsymbol{P} and decodes inside the Gabidulin code, while the Frobenius stability that powered earlier attacks is destroyed provided λ\lambda is large enough.

Coggia and Couvreur (Designs, Codes and Cryptography, 2020) showed that when k>(λ−1)n/λ+1k > (\lambda-1)n/\lambda + 1 (equivalently λ(n−k+1)<n\lambda(n-k+1) < n, i.e. public rate RpubR_{\mathrm{pub}} above roughly 1−1/λ1-1/\lambda), the dual of the public code is polynomial-time distinguishable from a random code by a linear-algebra dimension test on its Frobenius powers; this is the Coggia-Couvreur distinguisher. For masking dimension λ=2\lambda = 2 they turned the distinguisher into a polynomial-time key-recovery attack that outputs an equivalent decryption key (any data allowing decryption), and Ghatak (Designs, Codes and Cryptography, 2021) extended the attack to λ=3\lambda = 3.

Loidreau and Pham (arXiv:2112.12445, presented at WCC 2022) gave the general framework. For any λ\lambda in the distinguishable regime, linear algebra on the dual public code and its Frobenius powers first produces one-dimensional subspaces Ai\mathcal{A}_i (i=1,…,n−k−1i = 1, \ldots, n-k-1) spanned by vectors of the form h0+∑j=1λ−1βj[−i]hj\boldsymbol{h}_0 + \sum_{j=1}^{\lambda-1} \beta_j^{[-i]} \boldsymbol{h}_j, where h0,…,hλ−1\boldsymbol{h}_0, \ldots, \boldsymbol{h}_{\lambda-1} and the scalars β1,…,βλ−1\beta_1, \ldots, \beta_{\lambda-1} encode the secret mask ([−i][-i] denotes the ii-th inverse Frobenius power). Eliminating the hj\boldsymbol{h}_j yields a system of λ−1\lambda-1 multivariate polynomials P1,…,Pλ−1\mathcal{P}_1, \ldots, \mathcal{P}_{\lambda-1} over Fqm\mathbb{F}_{q^m} in the unknowns X1,…,Xλ−1X_1, \ldots, X_{\lambda-1}, of degrees qλ+1−qiq^{\lambda+1}-q^i, all satisfied by the secret coefficient vector β⃗\vec{\beta}; once one suitable root is found, the rest of the key recovery is linear algebra. Correctness and completeness of this construction are proved under three genericity hypotheses on the secret: non-vanishing of certain Moore-type determinants in the βj\beta_j (a full-rank condition on Frobenius powers of the secret coefficients), the expected dimension λ(n−k)+λ\lambda(n-k)+\lambda of the Frobenius span of the dual public code, and triviality of the stabilizer of β⃗\vec{\beta} under the projective linear group PGL(λ,Fq)\mathrm{PGL}(\lambda,\mathbb{F}_q) (invertible λ×λ\lambda \times \lambda matrices over Fq\mathbb{F}_q modulo scalar matrices, which acts on the masking coordinates by fractional-linear transformations). Under these assumptions and the absence of common factors among the Pi\mathcal{P}_i, the root set of the system is exactly one PGL(λ,Fq)\mathrm{PGL}(\lambda,\mathbb{F}_q)-orbit, of size ∏j=1λ−1(qλ+1−qj)=∣PGL(λ,q)∣\prod_{j=1}^{\lambda-1}(q^{\lambda+1}-q^j) = |\mathrm{PGL}(\lambda,q)|. For λ≤3\lambda \le 3 the system has at most two variables and one root can be found in polynomial time, by resultants together with univariate root-finding for λ=3\lambda = 3, with complexity O~(d2nlog⁡q)\tilde{O}(d^2 n \log q) for d=(q4−q)(q4−q2)d = (q^4-q)(q^4-q^2); complexity throughout is measured for fixed λ\lambda, counting Fqm\mathbb{F}_{q^m}-operations at unit cost as a function of nn, mm, and qq. For λ≥4\lambda \ge 4 the system has three or more variables and very large degrees, and general multivariate-polynomial solving is NP-hard, so the paper leaves the efficiency of the attack open; moreover, when the stabilizer assumption fails one falls back to an auxiliary multivariate quadratic (MQ) system, whose associated solvability problem is NP-complete. The paper's conclusion proposes as future work an extension of the attack to public codes of rate Rpub<1−1/λR_{\mathrm{pub}} < 1-1/\lambda, where the distinguisher, and hence the entire linear-algebraic pipeline feeding the polynomial system, fails.

The problem retains currency because the scheme family is actively developed: the masking idea underlies the LowMS rank-metric KEM (Designs, Codes and Cryptography, 2024) and a 2025 generalization by Nouetowa and Loidreau, while the best structural attack on practical parameters is currently the exponential combinatorial attack of Briaud and Loidreau (PQCrypto 2023), which applies precisely in the non-distinguishable regime where real parameters sit. The polynomial-time questions above govern the security boundary of the distinguishable regime and the strength of the algebraic attack route; a 2026 historical survey by Loidreau confirms that in the non-distinguishable regime only exponential attacks are known.

Problem Statement

Complete, or conclusively delimit, the Coggia-Couvreur-type structural key-recovery attack on Loidreau's rank-metric encryption scheme in the formulation established by Loidreau and Pham (arXiv:2112.12445).

Setting. Loidreau's scheme masks a kk-dimensional Gabidulin code Gk(g)⊂Fqmn\mathcal{G}_k(\boldsymbol{g}) \subset \mathbb{F}_{q^m}^n with an invertible matrix P\boldsymbol{P} whose entries lie in a secret λ\lambda-dimensional Fq\mathbb{F}_q-subspace V⊂Fqm\mathcal{V} \subset \mathbb{F}_{q^m}; the public key is Gpub=GP−1\boldsymbol{G}_{\mathrm{pub}} = \boldsymbol{G}\boldsymbol{P}^{-1}. Suppose the parameters lie in the distinguishable regime k>(λ−1)n/λ+1k > (\lambda-1)n/\lambda + 1 (equivalently λ(n−k+1)<n\lambda(n-k+1) < n, public rate above roughly 1−1/λ1-1/\lambda), where the dual-Frobenius dimension distinguisher applies.

Primary question. The Loidreau-Pham analysis reduces recovering an equivalent secret key to finding one root of an explicitly constructible system of λ−1\lambda-1 multivariate polynomials P1,…,Pλ−1\mathcal{P}_1, \ldots, \mathcal{P}_{\lambda-1} over Fqm\mathbb{F}_{q^m} in the unknowns X1,…,Xλ−1X_1, \ldots, X_{\lambda-1} (the coordinates of the secret mask), with deg⁡Pi=qλ+1−qi\deg \mathcal{P}_i = q^{\lambda+1}-q^i; once one suitable root β⃗\vec{\beta} is found, linear algebra over Fqm\mathbb{F}_{q^m} yields an equivalent decryption key. For λ=2\lambda = 2 and λ=3\lambda = 3 one root can be found in polynomial time, so the whole attack is polynomial time. For each fixed λ≥4\lambda \ge 4: does there exist a deterministic or probabilistic algorithm that, given the public key, finds one root of this system, and hence an equivalent secret key, in time polynomial in nn, mm, and qq (counting Fqm\mathbb{F}_{q^m}-operations at unit cost, with λ\lambda fixed)? Alternatively, is there another algebraic or algebraic-geometric reduction of the key-recovery search for λ≥4\lambda \ge 4 that achieves polynomial time?

Validity conditions. The reduction rests on genericity hypotheses that the source introduces as working assumptions rather than proved theorems: Assumptions (1)-(3) of Loidreau-Pham, namely the non-vanishing of the relevant Moore-type determinants in the secret coefficients, the expected dimension λ(n−k)+λ\lambda(n-k)+\lambda of the Frobenius span of the dual public code, and triviality of the PGL(λ,Fq)\mathrm{PGL}(\lambda,\mathbb{F}_q)-stabilizer of the secret coefficients; they are proved only conditionally and verified experimentally only at small parameters (for instance λ=3\lambda = 3, q=2q = 2), and their status for cryptographic parameter choices is part of the open picture (failure of the stabilizer assumption leads to an auxiliary multivariate quadratic system whose associated decision problem is NP-complete). The construction also uses a no-common-factor condition on the Pi\mathcal{P}_i; for λ≥4\lambda \ge 4 the system has at least three variables, where pairwise absence of common factors does not by itself imply a finite, Bezout-bounded root set, so the claimed structure that the root set equals one PGL(λ,Fq)\mathrm{PGL}(\lambda,\mathbb{F}_q)-orbit of size ∏j=1λ−1(qλ+1−qj)\prod_{j=1}^{\lambda-1}(q^{\lambda+1}-q^j) rests on an implicit zero-dimensionality hypothesis.

Complementary facet. The same source formulates as future work the extension of this key-recovery approach to public codes of rate Rpub<1−1/λR_{\mathrm{pub}} < 1-1/\lambda, where the distinguisher, and hence the entire linear-algebraic construction feeding the polynomial system, fails. There the best published attacks (Briaud-Loidreau, 2023) are exponential; whether a polynomial-time key-recovery attack exists in this regime, or whether the algebraic approach can be modified to reach it, remains open. The primary question and this low-rate extension together determine the polynomial-time boundary of structural key recovery for Loidreau's scheme over all masking dimensions λ\lambda and public-code rates. The fixed-λ≥4\lambda \ge 4 question in the distinguishable regime is resolved by a polynomial-time root-finding algorithm or an alternative polynomial-time algebraic (or algebraic-geometric) reduction of key recovery, and is resolved negatively by a conclusive proof that no such algorithm exists. The extension to public-code rates Rpub<1−1/λR_{\mathrm{pub}} < 1-1/\lambda is resolved by a polynomial-time key-recovery attack in that regime or by a proof that none exists. Settling the genericity hypotheses of Loidreau-Pham (Assumptions (1)-(3)) and the implicit zero-dimensionality hypothesis is part of what remains to be settled for the fixed-λ≥4\lambda \ge 4 question.

References

  1. Pierre Loidreau and Ba-Duc Pham, "An analysis of Coggia-Couvreur attack on Loidreau's rank-metric public key encryption scheme in the general case", arXiv:2112.12445 (2021), DOI 10.48550/arXiv.2112.12445, https://arxiv.org/abs/2112.12445
  2. Pierre Loidreau, "A New Rank Metric Codes Based Encryption Scheme", in Post-Quantum Cryptography (PQCrypto 2017), Lecture Notes in Computer Science 10346, pp. 3-17, Springer (2017), DOI 10.1007/978-3-319-59879-6_1, https://doi.org/10.1007/978-3-319-59879-6_1
  3. Daniel Coggia and Alain Couvreur, "On the security of a Loidreau rank metric code based encryption scheme", Designs, Codes and Cryptography 88(9):1941-1957 (2020), DOI 10.1007/s10623-020-00781-4, https://doi.org/10.1007/s10623-020-00781-4
  4. Anirban Ghatak, "Extending Coggia-Couvreur attack on Loidreau's rank-metric cryptosystem", Designs, Codes and Cryptography 90(1):215-238 (online November 2021), DOI 10.1007/s10623-021-00972-7, https://doi.org/10.1007/s10623-021-00972-7
  5. Wenshuo Guo and Fang-Wei Fu, "Two modifications for Loidreau's code-based cryptosystem", Applicable Algebra in Engineering, Communication and Computing 35(5):647-665 (online August 2022), DOI 10.1007/s00200-022-00577-0, https://doi.org/10.1007/s00200-022-00577-0
  6. Wenshuo Guo and Fang-Wei Fu, "McEliece-Type Encryption Based on Gabidulin Codes with No Hidden Structure", in Information Security and Cryptology (Inscrypt 2022), Lecture Notes in Computer Science 13837, pp. 108-126, Springer (2023), DOI 10.1007/978-3-031-26553-2_6, https://doi.org/10.1007/978-3-031-26553-2_6
  7. Pierre Briaud and Pierre Loidreau, "Cryptanalysis of Rank-Metric Schemes Based on Distorted Gabidulin Codes", in Post-Quantum Cryptography (PQCrypto 2023), Lecture Notes in Computer Science 14154, pp. 38-56, Springer (2023), DOI 10.1007/978-3-031-40003-2_2, https://doi.org/10.1007/978-3-031-40003-2_2
  8. Kayode Epiphane Nouetowa and Pierre Loidreau, "An Analysis of a Generalization of Loidreau's Encryption Scheme", in 2025 IEEE International Symposium on Information Theory (ISIT), IEEE (2025), DOI 10.1109/isit63088.2025.11195285, https://doi.org/10.1109/isit63088.2025.11195285
  9. Nicolas Aragon, Victor Dyseryn, Philippe Gaborit, Pierre Loidreau, Julian Renner, and Antonia Wachter-Zeh, "LowMS: a new rank metric code-based KEM without ideal structure", Designs, Codes and Cryptography 92(4):1075-1093 (2024), DOI 10.1007/s10623-023-01330-5, https://doi.org/10.1007/s10623-023-01330-5
  10. Pierre Loidreau, "Gabidulin codes based post-quantum encryption schemes", Mathematics and Education in Mathematics (Proceedings of the Fifty-Fifth Spring Conference of the Union of Bulgarian Mathematicians, Tryavna, April 2026), pp. 414-422 (2026), DOI 10.55630/mem.2026.55.414-422, https://doi.org/10.55630/mem.2026.55.414-422
  11. Alain Couvreur and Ilaria Zappatore, "An extension of Overbeck's attack with an application to cryptanalysis of Twisted Gabidulin-based schemes", arXiv:2305.01287 (2023), https://arxiv.org/abs/2305.01287
  12. R. Overbeck, "Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes", Journal of Cryptology 21(2):280-301 (2007), DOI 10.1007/s00145-007-9003-9, https://doi.org/10.1007/s00145-007-9003-9