PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Artyom Kuninets, Ekaterina Malygina, Evgeniy Melnichuk

arXiv:2609.17732v1cs.ITmath.IT

TL;DR

Algebraic-geometry codes were proposed to reduce McEliece key sizes, but previous structural attacks left some elliptic-code schemes considered secure. This paper gives a structural attack using three known evaluation points and an optimized version that needs none. The authors conclude that elliptic-code schemes, including ECC2 parameter sets, are insecure for arbitrary effective divisors and any number of inserted errors.

  • Problem

    Although structural attacks exposed vulnerabilities in several algebraic-geometry-code families, some elliptic-code schemes with additional key-generation conditions were until recently considered secure.

    Source: §1 · p. 2

  • Method

    The paper recovers the evaluation divisor from the curve, public generator matrix, and three known evaluation points, then uses curve automorphisms to replace those hints with pair enumeration for an equivalent-key attack.

    Source: §1 · p. 2

  • Results

    The authors conclude that elliptic-code McEliece schemes, including ECC2 parameter sets [10], are insecure for arbitrary effective divisors and any number of inserted errors.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The stated insecurity result includes ECC2 parameter sets and does not depend on restricting the number of inserted errors.

    Source: §1 · p. 2

    The average-case complexity estimate relies on a heuristic independence assumption for incorrect candidate pairs.

    Source: §3.4 · p. 15

Abstract

from arXiv · show

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 $\mathcal{O}(k^2n^2+|\mathcal{E}(\mathbb{F}_q)|+n)$ operations in $\mathbb{F}_q$ and succeeds with overwhelming probability, after which the second divisor is recovered in $\mathcal{O}\!\left(k^2n^2 + (|\mathcal{E}(\mathbb{F}_q)|-n)n^2\right)$ 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 $\mathcal{O}\!\left(k^2n^2 + q^2 + (|\mathcal{E}(\mathbb{F}_q)|-n)n^2\right)$ operations on average.

1 Introduction

The introduction describes how algebraic-geometry codes can reduce McEliece key sizes, while prior structural attacks left some elliptic-code schemes considered secure. The paper presents attacks that recover divisors for arbitrary effective divisors and any number of inserted errors, including an optimized version requiring no hints.

Introduction

  • Algebraic-geometry codes were proposed for McEliece to reduce key sizes relative to Goppa codes, whose large keys hinder practical integration despite fast encryption and decryption.The AG-code scheme was first proposed in, with later constructions reporting better parameters and smaller keys than Goppa codes.Source: §1 · p. 1
  • Earlier attacks on most algebraic-geometry-code families had limitations; ECC2 imposed additional code and parameter conditions and was until recently considered secure.Prior work included attacks on Reed–Solomon codes and attacks on elliptic and hyperelliptic codes requiring minimum-weight codewords, considered hard unless the code is MDS.Source: §1 · pp. 1–2

Our contribution.

  • The new attack applies to elliptic codes with arbitrary effective divisors and any number of inserted errors, recovering the evaluation divisor from the curve, public generator matrix, and three evaluation points.The authors also describe recovering the second divisor after this step.Source: §1 · p. 2
  • An optimized attack replaces the three known evaluation points with enumeration of one pair of field elements, exploiting curve automorphisms to recover an equivalent key on the public curve.The paper states that this version requires no knowledge of the evaluation-divisor points.Source: §1 · p. 2
  • The authors conclude that elliptic-code McEliece schemes, including ECC2 parameter sets [10], are insecure for arbitrary effective divisors and any number of inserted errors.The introduction states this conclusion after describing both attack variants.Source: §1 · p. 2

2 Preliminaries

The preliminaries define divisors and the associated Riemann–Roch spaces used to construct algebraic-geometry codes. They describe the code parameters and the generator matrix obtained by evaluating a basis of the space.

2.1 Algebraic geometry codes

  • A divisor on the curve is a finite formal sum of places; its coefficients are integers and all but finitely many are zero.Divisors form an abelian group, and the curve's F_q-rational points are denoted X(F_q).Source: §2.1 · p. 2
  • An effective divisor has nonnegative coefficients at every place, and the text uses coefficientwise comparison to define an order on divisors.The associated Riemann–Roch space is finite-dimensional, with dimension denoted ℓ(G).Source: §2.1 · pp. 2–3
  • The code associated with (D, G) is a linear code with length n = deg(D), dimension k = dim_Fq L(G), and minimum distance d.D consists of distinct rational points and has support disjoint from G; when 2g − 2 < deg(G) < n, k = deg(G) + 1 − g.Source: §2.1 · p. 3
  • Evaluating a basis of L(G) at the points of D gives a generator matrix for the algebraic-geometry code.The text introduces the evaluation map and states that the code parameters satisfy the Riemann–Roch bounds.Source: §2.1 · p. 3

3 Structural attacks on the McEliece cryptosystem based on elliptic codes

This section examines structural attacks on McEliece cryptosystems based on elliptic codes, including earlier filtration-based methods and recovery of key divisors. It covers an attack using three known evaluation points and an optimized variant that removes this hint by exploiting curve automorphisms and enumerating field-element pairs.

3.1 Computation of P-filtration for algebraic geometry code from [9]

  • The [9] P-filtration can be computed from the generator matrix alone, recursively deriving terms from preceding ones, starting with punctured and shortened codes.The punctured code deletes the coordinate for P; the shortened code selects codewords zero there before deleting that coordinate.Source: §3.1 · pp. 4–5

Error correcting pairs and arrays.

  • Prior error-correcting pairs enable decoding within their stated radius, arrays extend that radius, and power pairs can exceed half the minimum distance but fail near the Johnson bound.After recovering the pair, the attack decodes a shortened received vector and solves for the original codeword’s first coordinate.Source: Error correcting pairs and arrays · p. 5

3.2 Shkuratov’s attack on ECC2 scheme [1]

  • Shkuratov’s attack requires rare vector choices, each occurring with probability 1/q, and added searches, raising its analyzed cost to O(k^2n^2 + q^3n(n−k) + q).The original attack gives O((k^2 + q^2)n^2), but its correctness proof and complexity analysis contain inaccuracies.Source: §3.2 · pp. 5–6

3.3 New structural attack for arbitrary effective divisors G

  • For 5 ≤ deg(G) ≤ n/2−1, the new attack recovers D from E, Gpub, and three distinct points, for arbitrary effective divisors and any error count.The proof assumes the points of D are chosen uniformly at random from E(Fq).Source: §3.3 · pp. 6–7
  • The attack forms candidate sets of at most two points per divisor position and intersects sets from different hints to recover D.Each pair of hints separates candidates unless their doubled points coincide; if all three known points lie in one coset of E[2], the hints provide no separating information.Source: §3.3 · p. 9
  • The divisor D is recovered with probability 1 − O(|E(Fq)|^-2); failure probability is at most (N2 − 1)(N2 − 2) + 3N2(N2 − 1) + 3(N3 − 1), using N2 ≤ 4 and N3 ≤ 9.Source: §3.3 · p. 10
  • Given D, enumerating point pairs identifies supp(G) uniquely, and iterative code-membership tests recover multiplicities in O(deg(G)·(n + n^2)).The support test checks whether evaluations of the constructed functions belong to the code.Source: §3.3 · pp. 11–12
  • Without the three known points, the arbitrary-divisor attack remains polynomial-time, although its worst-case complexity increases by O(|E(F_q)|^3), approximately a factor q over the attack in.The attack can also be adapted to an unknown curve by recovering an isomorphic representation, similarly to.Source: §3.3 · p. 12
  • The stated recovery range 5 ≤ deg(G) ≤ n/2 − 1 extends to deg(G) ≥ n/2 + 1 by dualizing and to deg(G) = n/2 using the punctured code.Source: §3.3 · p. 13, §3.4 · p. 13

3.4 Optimized attack without “hints”

  • Using curve automorphisms, translations preserve the code while replacing three known evaluation points with a search over pairs of field elements, yielding an equivalent key on the given curve.The attack uses only the curve, an automorphism, and the public generator matrix, for char(F_q) > 3 and 5 ≤ deg(G) ≤ n/2 − 1.Source: §3.4 · p. 13
  • For q ≥ 64, incorrect pairs need at most 3 expected tests, reducing enumeration cost from O(nq^2) to O(q^2); when n ≥ 1 + 2 log_(1/ρ)(q), only the correct pair survives.The independence assumption behind the estimate is not implied by prior statements, but the estimate agrees with practical experiments, which found a unique passing pair for almost every code length tested.Source: §3.4 · p. 16
  • The optimized search succeeds in practice with a unique passing pair for almost every tested code length, although the independence assumption behind its average-case estimate is not proven.Source: §3.4 · p. 16

A.1 Riemann-Roch bases for arbitrary effective divisors from [12]

For a divisor supported on distinct rational points, the Riemann–Roch basis consists of the constant function and single-point and double-point basis functions. For a divisor kP, the basis functions depend on whether P is a 2-torsion point.

Divisors supported at one point

  • For G = kP with P not in E[2], the basis is {1, f2, …, fk}, where fs = y + As(x) and deg(As) ≤ s − 1.The functions satisfy v_{−P}(y + As(x)) ≥ s and are regular at every other point.Source: §A.1 · pp. 17–18
  • When P is in E[2], the basis uses a separate case, with a construction for the corresponding functions described in the appendix.Algorithm 6 is given as one possible method for constructing functions of the form fs(X, Y) = Y + As(X).Source: §A.1 · p. 18

General effective divisors

  • The basis for a divisor supported on distinct rational points combines the constant function with single-point and double-point basis functions.The single-point functions have pole divisor sP_i; the double-point functions have pole divisor P_i + P_j.Source: §A.1 · p. 18
  • For distinct points Pi and Pj, the double-point basis functions have simple poles at those two points, and Bi,j(x) is linear.The supplied description identifies the pole divisor as Pi + Pj.Source: §A.1 · p. 18
Loading 2609.17732v1…