pith. sign in

arxiv: 2603.09869 · v2 · submitted 2026-03-10 · 🧮 math.AG · cs.IT· math.IT

Linear Code Equivalence via Pl\"ucker Coordinates

Gessica Alecci , Giuseppe D'Alconzo This is my paper

Pith reviewed 2026-05-15 13:10 UTC · model grok-4.3

classification 🧮 math.AG cs.ITmath.IT
keywords linear code equivalencePlücker coordinatesinvariant rational functionsdiagonal actionGrassmannianpermutation matrixalgebraic cryptanalysismonomial matrices
0
0 comments X

The pith

Linear code equivalence reduces to constructing invariant polynomials with the permutation matrix as a root.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds an algebraic model for deciding whether two linear codes are equivalent under monomial transformations by isolating the permutation matrix component. It interprets the diagonal part of the transformation as a scaling action on Plücker coordinates of the Grassmannian and locates a set of algebraically independent invariant rational functions under that action. From any two equivalent codes the construction then produces explicit polynomials, each having the unknown permutation as a root. The approach avoids Reynolds operators and Gröbner bases yet yields polynomials whose size grows too quickly for current cryptographic parameters.

Core claim

We study the diagonal scaling action on linear codes via Plücker coordinates, determine algebraically independent generators of the field of invariant rational functions without Reynolds operators or Gröbner bases, and, for equivalent codes, explicitly construct polynomials in the unknown permutation matrix P that vanish at the correct value.

What carries the argument

The field of rational functions on the Grassmannian that remain invariant under diagonal scaling, generated without Reynolds operators or Gröbner bases and evaluated on Plücker coordinates of the two codes.

If this is right

  • Equivalent codes produce a system of polynomials whose common roots include the unknown permutation.
  • The generators of the invariant field can be obtained directly from the Plücker embedding without classical invariant-theory algorithms.
  • The reduction isolates the permutation-recovery subproblem as a root-finding task over the invariant field.
  • The same construction supplies a theoretical bridge between algebraic-geometry invariants and the decision version of linear code equivalence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the high-degree polynomials could be factored or reduced modulo smaller ideals, the method might yield practical attacks on monomial-equivalence problems.
  • The same invariant-field construction could be tested on other group actions that arise in code-based cryptography, such as equivalence under larger linear groups.
  • The explicit link between Plücker coordinates and permutation recovery suggests checking whether low-degree truncations of the invariants still separate orbits for small code lengths.

Load-bearing premise

The invariant rational functions admit a computable set of algebraically independent generators that can be written explicitly in terms of the permutation matrix without hidden relations.

What would settle it

An explicit small-parameter example of two equivalent codes for which at least one constructed invariant polynomial does not vanish at the true permutation matrix P.

Figures

Figures reproduced from arXiv: 2603.09869 by Gessica Alecci, Giuseppe D'Alconzo.

Figure 1
Figure 1. Figure 1: Algorithm InvGen for the computation of a minimal set of independent generators of K (Gr(k, n))Dn . Proof. For k ∈ {0, n}, the thesis easily follows. Let k /∈ {0, n}. The matrix Wk,n is the incidence matrix of t-subsets vs. k-subsets [29], with t = 1. Its rank over Z is given by rkZ (Wk,n) = Xt i=0  n i  −  n i − 1  . Hence, assuming n −1  = 0, the rank of Wk,n is n 0  − n −1  + n 1  − n 0  = n. N… view at source ↗
read the original abstract

The assumed hardness of the Linear Code Equivalence problem (LCE) lies at the core of the security of the LESS signature scheme and other signature schemes with advanced functionalities. The LCE problem asks to determine whether two linear codes are equivalent. This equivalence is represented by a monomial matrix $ Q$, i.e. the product of a diagonal matrix $D$ and a permutation matrix $P$. The recovery of $Q=DP$ is known to be reduced to the recovery of the permutation matrix $ P$ alone. Exploiting this fact, we construct an algebraic model for LCE involving only the matrix $P$. To this end, we study the action of monomial matrices on linear codes using tools from algebraic geometry, including Pl\"ucker coordinates and fields of invariant rational functions. In particular, we analyse the action of diagonal matrices on linear codes, which can be interpreted as diagonal scaling of the coordinates of elements of the Grassmannian. We propose a method to determine algebraically independent generators of the field of rational functions invariant under this action, without relying on Reynolds operators or Gr\"obner basis computations. Furthermore, given two equivalent codes, we apply our results to explicitly construct, for each invariant function, a polynomial having $P$ as a root. However, the resulting polynomials are not of practical use: their degrees are high for cryptographically relevant parameters, and the number of monomials grows exponentially, making them infeasible to manipulate. Despite this limitation, our results are of theoretical interest, as they constitute the first application of these tools to the cryptanalysis of LCE and provide insight into how algebraic geometry and invariant theory can be employed in Cryptography.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops an algebraic-geometric model for the Linear Code Equivalence (LCE) problem by interpreting monomial equivalence via the diagonal action on Plücker coordinates of the Grassmannian. It constructs a set of algebraically independent generators for the field of rational functions invariant under this action, without Reynolds operators or Gröbner bases, and shows that for equivalent codes these invariants yield explicit polynomials in the entries of the unknown permutation matrix P that vanish at P. The authors explicitly note that the resulting polynomials have high degree and exponentially many monomials, rendering them impractical for cryptographic parameters, and position the contribution as theoretical.

Significance. If the derivations hold, the work supplies the first explicit application of Plücker coordinates and invariant theory to LCE, giving a coordinate-wise, parameter-free description of the invariants and a direct reduction to polynomials in P. This provides geometric insight into the structure of the equivalence problem even though the explicit objects are acknowledged to be too large for practical cryptanalysis.

major comments (2)
  1. [Section on construction of invariant generators] The central construction of algebraically independent generators via weight-matching ratios (described after the reduction to the diagonal action) requires an explicit verification that the transcendence degree equals the expected dimension of the quotient variety; without this or a worked low-dimensional example confirming independence, the claim that the set generates the full invariant field remains unanchored.
  2. [Section on polynomial construction for equivalent codes] In the step that produces the polynomial having P as a root from each invariant (the paragraph following the generator construction), the substitution of the two codes into the invariant is not shown to be free of additional relations that could make the resulting polynomial identically zero or factor trivially; a concrete low-parameter example would confirm that the root property is non-vacuous.
minor comments (2)
  1. [Introduction and setup] Notation for the monomial matrix Q = D P is introduced early but the precise embedding of the diagonal scaling into the Plücker coordinates is only sketched; a short diagram or explicit coordinate formula would improve readability.
  2. [Abstract and conclusion] The abstract and conclusion both state that the polynomials are infeasible, yet no table or sentence gives even an order-of-magnitude count of monomials or degree for a toy parameter set (e.g., [n=8,k=4]); adding one such illustration would make the limitation concrete without altering the theoretical claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions. The comments highlight places where additional verification would strengthen the exposition. We have revised the manuscript to include a low-dimensional example confirming algebraic independence of the generators and a concrete small-parameter example showing that the constructed polynomials are non-vacuous. These additions address both major points without altering the theoretical claims.

read point-by-point responses

  1. Referee: The central construction of algebraically independent generators via weight-matching ratios (described after the reduction to the diagonal action) requires an explicit verification that the transcendence degree equals the expected dimension of the quotient variety; without this or a worked low-dimensional example confirming independence, the claim that the set generates the full invariant field remains unanchored.

    Authors: We agree that an explicit check of transcendence degree strengthens the argument. In the revised version we have inserted a new subsection containing a fully worked example for the Grassmannian Gr(2,4) over a small field. We compute the field of invariants generated by the weight-matching ratios, determine its transcendence degree by direct elimination, and verify that it equals the expected dimension of the quotient (equal to the number of independent ratios). This confirms algebraic independence and that the proposed set generates the full invariant field in this case; the general construction follows the same pattern. revision: yes

  2. Referee: In the step that produces the polynomial having P as a root from each invariant (the paragraph following the generator construction), the substitution of the two codes into the invariant is not shown to be free of additional relations that could make the resulting polynomial identically zero or factor trivially; a concrete low-parameter example would confirm that the root property is non-vacuous.

    Authors: We thank the referee for this observation. The revised manuscript now includes an explicit low-parameter example (two equivalent [4,2] codes over GF(5) related by a known permutation matrix P). For each invariant generator we form the difference of the two evaluations, clear denominators, and obtain a polynomial in the entries of P. We then verify by direct substitution that the polynomial is not identically zero, does not factor into trivial factors independent of P, and vanishes at the known equivalence matrix. This demonstrates that the root property holds non-vacuously for the constructed polynomials. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation constructs algebraically independent generators for the invariant rational functions under the diagonal monomial action on Plücker coordinates directly from the standard Grassmannian embedding and coordinate-wise weight-matching ratios. No parameters are fitted to data, no self-citations supply load-bearing uniqueness theorems, and the subsequent polynomial construction for the unknown permutation matrix P follows explicitly from evaluating the invariants on equivalent codes. The paper states the resulting high-degree polynomials are impractical for cryptographic sizes, confirming the reduction does not collapse to a tautology or prior author result by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The construction rests on standard facts about the Grassmannian, Plücker embedding, and the structure of invariant fields under torus actions; no new entities are postulated and no parameters are fitted to data.

axioms (2)
  • standard math The Plücker embedding realizes the Grassmannian as a projective variety whose coordinate ring carries a natural action of the diagonal torus.
    Invoked to interpret diagonal scaling of code coordinates as torus action on Plücker coordinates.
  • standard math The field of rational functions invariant under a torus action is finitely generated and can be described by algebraically independent generators.
    Used to guarantee the existence of the invariant generators without computing them via Reynolds operators.

pith-pipeline@v0.9.0 · 5606 in / 1487 out tokens · 60034 ms · 2026-05-15T13:10:38.421105+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    In: Moriai, S., Wang, H

    Alamati, N., De Feo, L., Montgomery, H., Patranabis, S.: Cryptographic group actions and applications. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 411–439. Springer, Cham (Dec 2020).https://doi.org/10.1007/978-3-030-64834-3_14

    work page doi:10.1007/978-3-030-64834-3_14 2020

  2. [2]

    Baldi, M., Barenghi, A., Beckwith, L., Biasse, J., Esser, A., Gaj, K., Mohajerani, K., Pelosi, G., Persichetti, E., Saarinen, M.O., Santini, P., Wallace, R.: LESS — Linear Equivalence SignatureScheme.Tech.rep.,NationalInstituteofStandardsandTechnology(2023),available athttps://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures

    work page 2023

  3. [3]

    International Journal of Computer Mathematics: Computer Systems Theory7(2), 112–128 (2022).https://doi.org/https://doi.org/10

    Barenghi, A., Biasse, J.F., Ngo, T., Persichetti, E., Santini, P.: Advanced signature function- alities from the code equivalence problem. International Journal of Computer Mathematics: Computer Systems Theory7(2), 112–128 (2022).https://doi.org/https://doi.org/10. 1080/23799927.2022.2048206

    work page arXiv 2022

  4. [4]

    Barenghi, A., Biasse, J.F., Persichetti, E., Santini, P.: LESS-FM: Fine-tuning signatures from thecodeequivalenceproblem.In:Cheon,J.H.,Tillich,J.P.(eds.)Post-QuantumCryptography - 12th International Workshop, PQCrypto 2021. pp. 23–43. Springer, Cham (2021).https: //doi.org/10.1007/978-3-030-81293-5_2

    work page doi:10.1007/978-3-030-81293-5_2 2021

  5. [5]

    Advances in Mathematics of Communications 17(1), 23–55 (2023).https://doi.org/https://doi.org/10.3934/amc.2022064

    Barenghi, A., Biasse, J.F., Persichetti, E., Santini, P.: On the computational hardness of the code equivalence problem in cryptography. Advances in Mathematics of Communications 17(1), 23–55 (2023).https://doi.org/https://doi.org/10.3934/amc.2022064

    work page doi:10.3934/amc.2022064 2023

  6. [6]

    Cryptology ePrint Archive, Report 2025/1017 (2025),https://eprint.iacr.org/ 2025/1017

    Battagliola, M., Mora, R., Santini, P.: Using the schur product to solve the code equivalence problem. Cryptology ePrint Archive, Report 2025/1017 (2025),https://eprint.iacr.org/ 2025/1017

    work page 2025

  7. [7]

    IEEE Transactions on Information Theory72(2), 1093–1108 (2026).https://doi.org/10

    Bennett, H., Bhatia, D., Biasse, J.F., Durisheti, M., LaBuff, L., Pallozzi Lavorante, V., Wait- kevich, P.: Asymptotic improvements to provable algorithms for the code equivalence problem. IEEE Transactions on Information Theory72(2), 1093–1108 (2026).https://doi.org/10. 1109/TIT.2025.3637683

    work page arXiv 2026

  8. [8]

    In: Dunkelman, O., Jacobson, Jr., M.J., O’Flynn, C

    Beullens, W.: Not enough LESS: An improved algorithm for solving code equivalence prob- lems overF q. In: Dunkelman, O., Jacobson, Jr., M.J., O’Flynn, C. (eds.) SAC 2020. LNCS, vol. 12804, pp. 387–403. Springer, Cham (Oct 2020).https://doi.org/10.1007/ 978-3-030-81652-0_15 18 G. Alecci and G. D’Alconzo

    work page 2020

  9. [9]

    In: Nitaj, A., Youssef, A.M

    Biasse, J.F., Micheli, G., Persichetti, E., Santini, P.: LESS is more: Code-based signatures without syndromes. In: Nitaj, A., Youssef, A.M. (eds.) AFRICACRYPT 20. LNCS, vol. 12174, pp. 45–65. Springer, Cham (Jul 2020).https://doi.org/10.1007/978-3-030-51938-4_3

    work page doi:10.1007/978-3-030-51938-4_3 2020

  10. [10]

    In: Chung, K.M., Sasaki, Y

    Budroni, A., Chi-Domínguez, J.J., D’Alconzo, G., Scala, A.J.D., Kulkarni, M.: Don’t use it twice! Solving relaxed linear equivalence problems. In: Chung, K.M., Sasaki, Y. (eds.) ASI- ACRYPT 2024, Part VIII. LNCS, vol. 15491, pp. 35–65. Springer, Singapore (Dec 2024). https://doi.org/10.1007/978-981-96-0944-4_2

    work page doi:10.1007/978-981-96-0944-4_2 2024

  11. [11]

    Cryptology ePrint Archive, Report 2025/227 (2025), https://eprint.iacr.org/2025/227

    Budroni, A., Esser, A., Franch, E., Natale, A.: Two is all it takes: Asymptotic and concrete im- provements for solving code equivalence. Cryptology ePrint Archive, Report 2025/227 (2025), https://eprint.iacr.org/2025/227

    work page 2025

  12. [12]

    Cryptography and Communications pp

    Budroni, A., Natale, A.: On the sample complexity of linear code equivalence for all code rates. Cryptography and Communications pp. 1–23 (2025).https://doi.org/https://doi. org/10.1007/s12095-025-00790-x

    work page doi:10.1007/s12095-025-00790-x 2025

  13. [13]

    In: El Mrabet, N., De Feo, L., Duquesne, S

    Chou, T., Niederhagen, R., Persichetti, E., Randrianarisoa, T.H., Reijnders, K., Samardjiska, S., Trimoska, M.: Take your MEDS: Digital signatures from matrix code equivalence. In: El Mrabet, N., De Feo, L., Duquesne, S. (eds.) AFRICACRYPT 23. LNCS, vol. 14064, pp. 28–52. Springer, Cham (Jul 2023).https://doi.org/10.1007/978-3-031-37679-5_2

    work page doi:10.1007/978-3-031-37679-5_2 2023

  14. [14]

    DCC93(7), 2415–2457 (2025).https://doi.org/10.1007/s10623-025-01576-1

    Chou, T., Persichetti, E., Santini, P.: On linear equivalence, canonical forms, and digital signatures. DCC93(7), 2415–2457 (2025).https://doi.org/10.1007/s10623-025-01576-1

    work page doi:10.1007/s10623-025-01576-1 2025

  15. [15]

    Cryptology ePrint Archive, Report 2006/291 (2006),https://eprint.iacr.org/2006/291

    Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006),https://eprint.iacr.org/2006/291

    work page 2006

  16. [16]

    Finite Fields and Their Applications99, 102476 (2024).https://doi.org/ https://doi.org/10.1016/j.ffa.2024.102476

    D’Alconzo, G., Di Scala, A.J.: Representations of group actions and their applications in cryptography. Finite Fields and Their Applications99, 102476 (2024).https://doi.org/ https://doi.org/10.1016/j.ffa.2024.102476

    work page doi:10.1016/j.ffa.2024.102476 2024

  17. [17]

    Cryptology ePrint Archive, Paper 2025/397 (2025),https://eprint.iacr

    Duong,D.H.,Khuc,X.T.,Qiao,Y.,Susilo,W.,Zhang,C.:Blindsignaturesfromcryptographic group actions. Cryptology ePrint Archive, Paper 2025/397 (2025),https://eprint.iacr. org/2025/397

    work page 2025

  18. [18]

    Designs, Codes and Cryptography94(2), 42 (2026).https: //doi.org/https://doi.org/10.1007/s10623-025-01787-6

    D’Alconzo, G., Meneghetti, A., Signorini, E.: Group factorisation for smaller signatures from cryptographic group actions. Designs, Codes and Cryptography94(2), 42 (2026).https: //doi.org/https://doi.org/10.1007/s10623-025-01787-6

    work page doi:10.1007/s10623-025-01787-6 2026

  19. [19]

    Eisenbud, D.: Commutative Algebra: with a View Toward Algebraic Geometry, vol. 150. Springer Science & Business Media (2013)

    work page 2013

  20. [20]

    Gatto, L.: Schubert Calculus: An Algebraic Introduction, vol. 25. Instituto Nacional de Matemática Pura e Aplicada (2005)

    work page 2005

  21. [21]

    The American Mathematical Monthly79(10), 1061–1082 (1972).https://doi.org/https://doi.org/10.1080/00029890.1972.11993188

    Kleiman, S.L., Laksov, D.: Schubert calculus. The American Mathematical Monthly79(10), 1061–1082 (1972).https://doi.org/https://doi.org/10.1080/00029890.1972.11993188

    work page doi:10.1080/00029890.1972.11993188 1972

  22. [22]

    NIST: Post-quantum cryptography: Digital signature schemes.https://csrc.nist.gov/ Projects/pqc-dig-sig/standardization(2023), accessed: 2024-04-18

    work page 2023

  23. [23]

    In: Niederhagen, R., Saari- nen, M.J.O

    Nowakowski, J.: An improved algorithm for code equivalence. In: Niederhagen, R., Saari- nen, M.J.O. (eds.) Post-Quantum Cryptography - 16th International Workshop, PQCrypto 2025, Part I. pp. 71–103. Springer, Cham (Apr 2025).https://doi.org/10.1007/ 978-3-031-86599-2_3

    work page 2025

  24. [24]

    In: Guo, J., Steinfeld, R

    Persichetti, E., Santini, P.: A new formulation of the linear equivalence problem and shorter LESS signatures. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023, Part VII. LNCS, vol. 14444, pp. 351–378. Springer, Singapore (Dec 2023).https://doi.org/10.1007/ 978-981-99-8739-9_12

    work page 2023

  25. [25]

    In: Algebraic Geometry IV: Linear Algebraic Groups Invariant Theory, pp

    Popov, V.L., Vinberg, E.B.: Invariant Theory. In: Algebraic Geometry IV: Linear Algebraic Groups Invariant Theory, pp. 123–278. Springer (1994)

    work page 1994

  26. [26]

    Saeed, M.A.: Algebraic approach for code equivalence. Ph.D. thesis, Normandie Université; University of Khartoum (2017) Linear Code Equivalence via Plücker Coordinates 19

    work page 2017

  27. [27]

    Phd thesis, Norwegian University of Science and Technology (2012)

    Stolbunov, A.: Cryptographic schemes based on isogenies. Phd thesis, Norwegian University of Science and Technology (2012)

    work page 2012

  28. [28]

    Springer (2008)

    Sturmfels, B.: Algorithms in Invariant Theory. Springer (2008)

    work page 2008

  29. [29]

    k-subsets

    Wilson, R.M.: A diagonal form for the incidence matrices of t-subsets vs. k-subsets. European Journal of Combinatorics11(6), 609–615 (1990).https://doi.org/https://doi.org/10. 1016/S0195-6698(13)80046-7

    work page 1990