A Polynomial-Time Attack on the McEliece Cryptosystem on Elliptic Codes with Arbitrary Divisors

Abstract

The McEliece cryptosystem based on algebraic geometry codes has been proposed as a way to reduce the key size of code-based cryptography, but several structural attacks have demonstrated the vulnerability of particular families of algebraic geometry codes. Despite this, until recently, there remained schemes and parameter sets that were not vulnerable to any known attack. We propose a new structural attack with ``hints'' that applies to elliptic codes with arbitrary effective divisors. In particular, we prove that, given the elliptic curve, the public generator matrix, and three points from the evaluation divisor, the entire divisor can be recovered in polynomial time, independently of the number of errors used in the cryptosystem. The attack requires 𝒪(k²n²+|ℰ(𝔽_q)|+n) operations in 𝔽_q and succeeds with overwhelming probability, after which the second divisor is recovered in 𝒪 (k²n² + (|ℰ(𝔽_q)|−n)n²) operations. We further propose an optimized version of the attack that requires no additional information at all. Exploiting the action of the automorphisms of the curve, the three known points are replaced by the enumeration of a single pair of field elements, which yields an equivalent key on the given public curve in 𝒪 (k²n² + q² + (|ℰ(𝔽_q)|−n)n²) operations on average.

The square function estimates for cones in arbitrary dimensions and elliptic quadrics
Faruk Temur
arXiv4 Nov 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Regularity and Rivière's GL(m)-Gauge Construction for Elliptic Systems with Antisymmetric Potentials in Arbitrary Dimensions
Carolin Bayer
arXiv2 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEs Geometry & topologyarXiv
On Polynomial Complex Hessian Equations I: Non-Linear Non-Spectral Elliptic Hessian Equations on Riemannian Manifolds
Rémi Delloque
arXiv5 Oct 2026PreprintCC BY 4.0Full textAnalysis & PDEs Geometry & topologyarXiv
Elliptic Fekete points: separation, Riesz energies, and polynomial conditioning
Ujué Etayo
arXiv30 Oct 2026PreprintCC BY-NC-ND 4.0Full textAnalysis & PDEsarXiv
Exact Solution for a Class of First-Order Reflected Equations Involving a Polynomial-Type Forcing Term of Arbitrary Finite Degree
Abdulrahman B. Albidah
Axioms1 Sep 2026Peer-reviewedCC BYFull textGeneral mathematicsDOAJ

Cite

BibTeX RIS

BibTeX

@misc{kuninets2026polynomialtime,
  title = {{A Polynomial-Time Attack on the McEliece Cryptosystem on Elliptic Codes with Arbitrary Divisors}},
  author = {Artyom Kuninets and Ekaterina Malygina and Evgeniy Melnichuk},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.17732},
  eprint = {2609.17732},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.17732},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - A Polynomial-Time Attack on the McEliece Cryptosystem on Elliptic Codes with Arbitrary Divisors
AU  - Artyom Kuninets
AU  - Ekaterina Malygina
AU  - Evgeniy Melnichuk
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.17732
UR  - https://arxiv.org/abs/2609.17732
AB  - The McEliece cryptosystem based on algebraic geometry codes has been proposed as a way to reduce the key size of code-based cryptography, but several structural attacks have demonstrated the vulnerability of particular families of algebraic geometry codes. Despite this, until recently, there remained schemes and parameter sets that were not vulnerable to any known attack. We propose a new structural attack with ``hints'' that applies to elliptic codes with arbitrary effective divisors. In particular, we prove that, given the elliptic curve, the public generator matrix, and three points from the evaluation divisor, the entire divisor can be recovered in polynomial time, independently of the number of errors used in the cryptosystem. The attack requires 𝒪(k^2n^2+|ℰ(𝔽_q)|+n) operations in 𝔽_q and succeeds with overwhelming probability, after which the second divisor is recovered in 𝒪 (k^2n^2 + (|ℰ(𝔽_q)|−n)n^2) operations. We further propose an optimized version of the attack that requires no additional information at all. Exploiting the action of the automorphisms of the curve, the three known points are replaced by the enumeration of a single pair of field elements, which yields an equivalent key on the given public curve in 𝒪 (k^2n^2 + q^2 + (|ℰ(𝔽_q)|−n)n^2) operations on average.
ER  -

Abstract

Related

Cite