Source-linked AI summary
A General Construction of Codes from Drinfeld Modules
Alessandro Giannoni, Giacomo Micheli, Mihran Papikian
TL;DR
The paper asks how restriction-to-torsion constructions from Drinfeld modules can produce additive rank- and sum-rank-metric codes beyond the semifield setting. It restricts bounded-degree morphisms to prime-to-characteristic torsion, obtaining asymptotically optimal families and an explicit MSRD family with decoding results subject to computability conditions.
Problem
The paper develops the restriction-to-torsion viewpoint beyond the full-rank semifield setting and places it in the sum-rank metric.
Method
The paper restricts bounded-degree Drinfeld-module morphisms simultaneously to prime-to-characteristic torsion modules and derives filter- and skew-CRT-based decoding equations.
Results
The constructions have normalized additive Singleton defects tending to zero; in characteristic (T), ϕT = τ^r gives an explicit MSRD family with an exact poly-skew/sum-rank metric identity.
Takeaways & Limitations
The characteristic-(T) family has a polynomial-time unique decoder up to the full sum-rank unique-decoding radius, while the general decoder is effective when the required bases and restriction maps are computable.
Abstract
from arXiv · showhide
We construct additive rank-metric and sum-rank-metric codes from Drinfeld modules by restricting bounded-degree morphisms to prime-to-characteristic torsion. For supersingular Drinfeld modules of rank $r$ in characteristic $\mathfrak{p}$ of degree $d$, the stabilization formula for morphism spaces yields rank-metric codes of $\mathbb{F}_q$-dimension $mrt-c$ and minimum distance $r-t+1$, where $c=r(r-1)(d-1)/2$. Simultaneous restriction to $\ell$ distinct degree-$m$ torsion modules gives additive sum-rank codes of the same dimension and minimum distance at least $\ell r-t+1$. Their normalized Singleton defects tend to zero, while in characteristic $(T)$ the module $φ_T=τ^r$ makes the defect vanish and produces an explicit MSRD family. We identify this family with a skew Chinese remainder theorem code supported on central skew polynomials and prove that its poly-skew weight is exactly $m$ times its sum-rank weight. This gives a specialized Singleton-type bound and a polynomial-time unique decoder up to the full sum-rank unique-decoding radius. We also derive a Welch-Berlekamp-type filter equation for the general supersingular sum-rank construction; it becomes an effective decoder whenever bases of the relevant morphism spaces and the restriction maps are computable.
1. Introduction
The paper extends restriction-to-torsion constructions from rank-metric codes to additive sum-rank codes, using bounded-degree morphisms of Drinfeld modules. It obtains asymptotically optimal families, an explicit MSRD family in characteristic (T), and decoding procedures with stated effectiveness conditions.
- Construction: Restriction to torsion converts Fq-linear spaces of Drinfeld-module morphisms into additive rank-metric codes by measuring kernels on torsion.The construction applies to prime-to-characteristic torsion and reduces rank analysis to kernel dimensions.
- Sum-rank codes: Simultaneous restriction to ℓ distinct degree-m torsion modules produces additive sum-rank codes with the same dimension and minimum distance at least ℓr − t + 1.Chinese remainder decomposition converts blockwise kernel dimensions into a global root count.
- Optimality: The normalized additive Singleton defect tends to zero, while characteristic (T) with ϕT = τ^r gives c = 0 and an MSRD family.The explicit family is supported by central skew polynomials and is identified with a skew CRT realization.
- Decoding: The paper derives a Welch–Berlekamp-type filter equation for general supersingular codes and a polynomial-time skew CRT decoder for the explicit characteristic-(T) family.The general decoder is effective when the relevant morphism-space bases and restriction matrices are computable.
- Multishot motivation: Joint sum-rank coding matches a multishot channel with a global error budget better than protecting each shot independently.The normalized rates are 1 − 2e/(ℓr) for the joint strategy and 1 − 2e/r for the separated strategy.
2. Background
This section introduces rank and sum-rank metrics, their Singleton-optimal code classes, the multishot channel, and the Drinfeld-module algebra underlying the constructions. It also explains why joint sum-rank coding is suited to multishot errors with a global budget.
- Optimal codes: Codes attaining the rank- and sum-rank Singleton bounds are called MRD and MSRD codes, respectively.The section also defines additive variants as Fq-linear subspaces, which need not be Fqm-linear.
- Multishot channel: A multishot transmission sends an ℓ-tuple of matrices, with admissible errors constrained by total sum-rank weight.Nearest-neighbor decoding corrects all errors of parameter e when the minimum sum-rank distance exceeds 2e.
- Joint versus separated coding: For ℓ > 1 and 2e < r, a joint MSRD code has normalized rate 1 − 2e/(ℓr), compared with 1 − 2e/r for independent one-shot MRD codes.The comparison concerns a genuinely multishot channel with a global error budget.
- Twisted-polynomial background: Twisted polynomials encode additive polynomials through the relation τ^i ↦ Z^{q^i}, providing the algebraic language for Drinfeld-module actions.A Drinfeld module is determined by the image of T, with rank encoded by the highest twisted degree.
- Drinfeld modules: Drinfeld modules are Fq-algebra homomorphisms from A = Fq[T] into twisted-polynomial rings, and their morphisms induce linear maps on prime-to-characteristic torsion.For a prime f of degree m and rank r, the f-torsion is an r-dimensional vector space over Fqm.
3. The Constructions
The paper constructs additive rank- and sum-rank-metric codes by restricting bounded-degree Drinfeld-module morphisms to prime-to-characteristic torsion. Stabilization formulas yield asymptotically optimal families, while characteristic (T) gives an explicit MSRD construction.
- From Morphisms to Rank-Metric Codes: Restriction to prime-to-characteristic torsion converts Fq-linear morphism spaces into additive rank-metric codes.The induced matrix rank equals r minus the Fqm-dimension of the morphism's kernel on torsion.
- An Asymptotically MRD Construction: For bounded-degree supersingular morphisms, the rank-metric code has dimension mrt − c and minimum distance r − t + 1, with c = r(r − 1)(d − 1)/2.The code is exactly c below the additive Singleton bound for its minimum rank distance.
- An Asymptotically MRD Construction: As m →∞, the normalized Singleton defect of the rank-metric family tends to zero, making it asymptotically MRD.This conclusion holds for fixed r, t, and d.
- An Asymptotically MSRD Construction: Simultaneous restriction to ℓ distinct degree-m torsion modules produces additive sum-rank codes whose restriction map is injective and whose distance is at least ℓr − t + 1.The Chinese remainder decomposition combines blockwise kernel dimensions into a global root count.
4. Filter Equations and Skew CRT Decoding
The paper derives a general Welch–Berlekamp-type filter decoder for supersingular sum-rank codes and an explicit skew CRT decoder in characteristic (T). The characteristic-(T) realization has exact metric correspondence and reaches the full sum-rank unique-decoding radius with polynomial-time online complexity after precomputation.
- General filter decoder: The filter decoder solves simultaneously for an error filter v and filtered numerator N using an Fq-linear system, then recovers the message by left division.The unknowns satisfy N = vu for every nonzero valid solution.
- General filter decoder: The two degree conditions balance filter existence against uniqueness by forcing Z = N − vu to vanish through the root-space bound.The first condition ensures a nonzero filter exists; the second eliminates spurious solutions.
- General filter decoder: Algorithm 4.2 corrects every error tuple of sum-rank weight at most ελ under the stated dimension and degree conditions.It outputs a candidate message or failure after filtering, division, and residual verification.
- Characteristic-(T) specialization: In characteristic (T), the general filter decoder reaches the full unique-decoding radius.Here the admissibility condition reduces to 2ε + t ≤ ℓr.
- Characteristic-(T) specialization: The characteristic-(T) code is identified with a central skew CRT code whose restriction maps form an isomorphism and whose poly-skew metric rescales to the sum-rank metric by 1/m.Its exact minimum sum-rank distance is ℓr − t + 1, and central support explains the strengthened Singleton-type bound.
- Skew CRT decoder: After CRT data and restriction maps are precomputed, the skew CRT decoder has online key-equation complexity O(N^ω) over F_qr.Coordinate conversions and Ore-polynomial divisions are polynomial-time operations with effective finite-field representations.
5. Cryptographic Outlook
The paper proposes Drinfeld-module codes as potential hidden-algebraic constructions for public-key and multishot network-coding settings. The cryptographic discussion remains prospective because the security observations are heuristic and no security proof is given.
- Hidden algebraic descriptions: A public generator matrix can conceal the Drinfeld module, torsion primes, bases, and restriction or CRT data used for efficient decoding.This separates the public code representation from its private algebraic decoding description.
- Hidden algebraic descriptions: Existing structural attacks on Reed–Solomon, Gabidulin, and linearized Reed–Solomon codes do not immediately apply in the same form when evaluation data and Moore matrices remain private.The paper frames recovery of an equivalent hidden realization or decoder as a reconstruction problem.
- Scope and caveats: The proposed cryptographic advantage is conditional on the reconstruction problem being hard, and the observations are explicitly heuristic rather than a security proof.The codes are presented as potential candidates for secure multishot constructions after suitable nested or dual families are selected.