PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear Complementary Pairs of MDS Codes from Elliptic Curves

Adler Marques

arXiv:2610.29835v1cs.ITmath.AGmath.ITmath.NT

TL;DR

Constructing LCPs whose constituent elliptic codes are both MDS is mathematically challenging, and evaluation over all rational points has a geometric limitation. The paper develops geometric conditions and subgroup-coset constructions, proving the limitation and giving explicit infinite families over Mordell and supersingular curves.

  • Problem

    Constructing LCPs of MDS codes is mathematically challenging, and elliptic-curve evaluation over all rational points can prevent both constituent codes from being MDS.

    Source: §1 · p. 1, §3.1 · p. 5

  • Method

    The paper derives geometric conditions for elliptic-code LCPs and constructs evaluation divisors using subgroup cosets.

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

  • Results

    The paper proves an all-rational-points non-existence result and derives explicit infinite families of MDS-code LCPs from Mordell and supersingular curves.

    Source: §1 · p. 2, §3.1 · p. 5, §5 · p. 13

  • Takeaways & Limitations

    Restricting evaluation to subgroup cosets provides constructions of LCPs whose elliptic-code constituents are strictly MDS.

    Source: §1 · p. 2

    The low-dimension non-MDS assumption requires each k-subset sum map on the evaluation points to be surjective for every 1 ≤ k < α.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

In this paper, we investigate the Linear Complementary Pairs (LCPs) of Maximum Distance Separable (MDS) codes that arise from elliptic curves. We establish geometric conditions for LCPs of elliptic codes and prove that they cannot consist entirely of MDS codes when evaluated over all rational points of the curve. To address this, we construct LCPs of MDS elliptic codes by restricting evaluation divisors to subgroup cosets. We apply this method to obtain explicit infinite families of LCPs of MDS codes over Mordell and supersingular elliptic curves, including large-length constructions over quadratic extensions.

1. Introduction

LCPs of MDS codes offer the strongest possible security parameter for masking schemes, but constructing them from elliptic codes faces a geometric obstruction. The paper develops subgroup-coset constructions and applies them to explicit infinite families.

1. Introduction

  • LCPs of MDS codes provide the strongest possible security parameter for masking schemes against side-channel and fault-injection attacks.The parameter is min{d(C), d(D⊥)}.Source: §1 · p. 1
  • Evaluating over an entire elliptic-curve subgroup introduces a zero-sum relation that forces coordinate dependencies and destroys the MDS property.This rigidity helps explain why existing prime-field constructions are typically shorter or almost-MDS.Source: §1 · p. 1
  • Excluding a single low-order rational point from a union of subgroup cosets breaks that relation and yields LCPs whose constituent elliptic codes are strictly MDS.Source: §1 · p. 2
  • The paper establishes geometric conditions and an all-rational-points MDS limitation, then constructs explicit infinite families over Mordell and supersingular curves, including large-length families over quadratic extensions.The quadratic-extension construction has length n = s(p+1)−1.Source: §1 · p. 2

2. Preliminaries

The preliminaries set up linear-code and elliptic-curve notation, define elliptic evaluation codes, and translate LCP conditions into divisor properties. These tools support the paper’s later geometric analysis.

2.1. Linear Codes and Linear Complementary Pairs.

  • A linear code is specified by length, dimension, and minimum distance; MDS codes attain the Singleton bound, and dual codes of MDS codes are MDS.Source: §2.1 · p. 2
  • An LCP consists of codes with complementary dimensions and trivial intersection, equivalently a direct-sum decomposition of the ambient vector space.Source: §2.1 · p. 2

2.2. Elliptic Curves.

  • Rational points of an elliptic curve form a finite abelian group, and the Abel–Jacobi theorem identifies its group law with degree-zero divisor classes.The paper distinguishes scalar multiplication [m]P in the group from the divisor mP.Source: §2.2 · p. 3

2.3. Elliptic Codes.

  • An elliptic code evaluates functions in a Riemann–Roch space at distinct rational points, and its parameters make it either MDS or almost-MDS.The stated minimum distance is n−k or n−k+1.Source: §2.3 · pp. 3–4

2.4. LCP of AG Codes.

  • For AG codes, an LCP can be certified by complementary Riemann–Roch dimensions together with non-special gcd and lmd−D divisors of degree g−1.The code intersection analysis involves functions whose difference vanishes on D.Source: §2.4 · p. 4

3. LCP of MDS Elliptic Codes

The section gives geometric conditions for LCPs of elliptic codes and shows why MDS constituents can fail under broad evaluation. It then constructs LCPs of MDS elliptic codes using evaluation divisors supported on subgroup cosets.

3.1. General Conditions and MDS Limitations.

  • For elliptic codes with 0 < deg(G), deg(H) < n, degree balance and two degree-zero group-sum conditions suffice for an LCP.The conditions are deg(G)+deg(H)=n, σ(gcd(G,H))≠O, and σ(lmd(G,H))≠σ(D).Source: §3.1 · p. 5
  • If no elliptic code of dimension below α is MDS, any LCP containing a code of dimension below α has neither constituent MDS.The restriction follows by passing to the dual constituent, whose divisor has the same degree.Source: §3.1 · p. 5
  • The low-dimension non-MDS obstruction occurs only when evaluation uses all Fq-rational points of the elliptic curve.Source: §3.1 · p. 5

3.2. Constructions of LCPs of MDS Elliptic Codes.

  • The construction chooses cosets [λj]P0 ⊕ H and imposes congruence conditions on their point allocations to obtain MDS constituents and an LCP.The evaluation divisor has n = sm−1 points, with m−1 from the first coset and m from each remaining coset.Source: §3.2 · pp. 6, 8
  • Coset-based constructions yield LCPs of MDS elliptic codes with parameters [n, a + n −b, b −a + 1]q and [n, b −a, n −b + a + 1]q, respectively.The evaluation divisor is built from subgroup cosets while excluding rational points; Theorem 3.4 gives conditions for the resulting pair.Source: §3.2 · p. 6
  • For a single coset with D supported on (P0 ⊕ H)\{P0}, the construction gives an LCP of MDS elliptic codes when 0 < b−a < n and its stated congruence conditions hold.The resulting parameters are [n, a + n −b, b −a + 1]q and [n, b −a, n −b + a + 1]q.Source: §3.2 · p. 8

4. Examples from Explicit Elliptic Curves

The section specializes the coset construction to Mordell and supersingular elliptic curves, producing explicit LCPs of MDS codes. It includes single-coset families over prime fields and multi-coset families over supersingular curves, including an infinite family over quadratic extensions.

Mordell curves

  • Over Fp with p ≡ 5 or 11 (mod 18), Mordell curves yield LCPs with parameters [n, n − b + 1, b] and [n, b − 1, n − b + 2], where n = (p − 2)/3.The construction uses a subgroup coset with its order-3 point P0 excluded and requires 1 < b < n + 1, b not congruent to 0 or n modulo 3.Source: §4 · pp. 8–9

Supersingular curves over prime fields

  • For p ≡ 3 (mod 8), the curve y2 = x3 + x over Fp gives LCPs with parameters [n, n − b + 1, b] and [n, b − 1, n − b + 2], where n = (p − 3)/4.The allowed b values satisfy 1 < b < n + 1 and avoid 0 and n modulo 4.Source: §4 · pp. 8–10

Mordell curves

  • For p = 47, the Mordell-curve example yields length-15 MDS code pairs for b ∈ {2, 4, 5, 7, 8, 10, 11, 13, 14}.The curve uses a subgroup of order 16 and an order-3 point.Source: §4 · p. 10

Multi-coset example

  • For p = 19, the two-coset construction over F19 yields length-9 MDS code pairs for b = 2 or 6.The evaluation divisor has degree 9 and is formed from two subgroup cosets.Source: §4 · pp. 10–11

Large-length families over quadratic extensions

  • For p ≥ 7 with p ≡ 3 (mod 4), the quadratic-extension construction gives LCPs of MDS codes over Fp2 with length n = s(p + 1) − 1 and parameters [n, n − k, k + 1] and [n, k, n − k + 1].Here 1 ≤ s ≤ (p − 1)/2 and k ≥ 1 must satisfy k(2s − 1) + 2 ≤ p.Source: §4 · p. 11
  • In the p = 19 quadratic-extension example, increasing s produces lengths from 19 to 179, while the bound forces k = 1 for s ≥ 5.At s = 9, the length is 179 and the component dimensions are 1 and 178.Source: §4 · p. 12

5. Conclusion

The paper establishes geometric conditions for LCPs of elliptic codes and proves that evaluating over all rational points cannot yield an LCP consisting entirely of MDS codes. It overcomes this obstruction with a multi-coset construction, deriving explicit infinite families over Mordell and supersingular curves and identifying extension to higher genus as future work.

Conclusion

  • The Abel–Jacobi theorem gives sufficient geometric conditions for LCPs of elliptic codes, and evaluation over all rational points cannot produce an LCP whose constituents are all MDS.The paper reports that its explicit families and computational parameters were verified using MAGMA.Source: §5 · pp. 12–13
  • A multi-coset algebraic construction breaks the zero-sum relation and yields exact parameters for explicit infinite families of MDS-code LCPs from Mordell and supersingular curves.The paper suggests extending the framework to optimal codes using divisor groups of curves of higher genus.Source: §5 · p. 13
Loading 2610.29835v1…