pith. sign in

arxiv: 2603.23230 · v2 · submitted 2026-03-24 · 💻 cs.CR · cs.IT· math.IT

The Power of Power Codes: New Classes of Easy Instances for the Linear Equivalence Problem

Michele Battagliola , Anna-Lena Horlemann , Abhinaba Mazumder , Rocco Mora , Paolo Santini , Michael Schaller , Violetta Weger This is my paper

Pith reviewed 2026-05-15 00:34 UTC · model grok-4.3

classification 💻 cs.CR cs.ITmath.IT
keywords linear equivalence problempower codesFrobenius automorphismHermitian hullpermutation equivalencepost-quantum cryptographycode-based cryptographyalgebraic cryptanalysis
0
0 comments X

The pith

Power codes combined with Frobenius automorphisms and Hermitian hulls identify many new easy instances for the linear equivalence problem.

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

The paper extends the Schur-product technique for solving the permutation equivalence problem to the more general linear equivalence problem by introducing power codes. These are combined with Frobenius automorphisms and Hermitian hulls to produce broad families of linear codes whose equivalences can be recovered efficiently. A sympathetic reader would care because LEP serves as a hardness assumption for post-quantum signature schemes such as LESS, so new easy instances directly affect the concrete security of those constructions. The authors also give an improved reduction from LEP to PEP when the entries of the monomial matrix lie in a suitable subgroup of the multiplicative group of the base field.

Core claim

By generalizing the Schur-product method to power codes and folding in Frobenius automorphisms together with Hermitian hulls, the authors obtain many new infinite families of linear codes for which the linear equivalence problem admits an efficient algebraic solution. They further show that whenever the coefficients of the unknown monomial matrix belong to a proper subgroup of the multiplicative group, the problem reduces to an instance of the permutation equivalence problem that can be solved with lower complexity.

What carries the argument

Power codes, obtained by raising codeword coordinates to a fixed power and taking linear spans, used together with Frobenius automorphisms to expose hidden equivalences and Hermitian hulls to certify them.

If this is right

  • Numerous previously unclassified families of linear codes now admit efficient equivalence recovery.
  • Security proofs for code-based schemes must exclude or account for these power-code families.
  • The subgroup condition yields a strictly faster reduction from LEP to PEP than the generic case.
  • The same algebraic toolkit can be applied to other isometry problems between linear codes.

Where Pith is reading between the lines

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

  • Designers of future code-based primitives should deliberately avoid power-code structures when sampling public keys.
  • The method may extend to equivalence problems over non-linear or constant-weight codes once suitable power analogs are defined.
  • Concrete implementations on small fields would produce explicit lists of easy instances that can be used for benchmarking.
  • If power codes capture most algebraic weaknesses, then hardness of LEP may concentrate in codes whose hulls are trivial.

Load-bearing premise

The chosen power codes and their associated hulls must admit the expected dimension and intersection behavior over the finite field, and the monomial-matrix coefficients must lie inside the subgroup required for the improved reduction.

What would settle it

Construct two linear codes from a power-code family over a small finite field, apply a random monomial equivalence, and check whether the algebraic procedure recovers the equivalence in polynomial time; failure on a non-negligible fraction of trials would falsify the claim.

read the original abstract

Given two linear codes, the Linear Equivalence Problem (LEP) asks to find (if it exists) a linear isometry between them; as a special case, we have the Permutation Equivalence Problem (PEP), in which isometries must be permutations. LEP and PEP have recently gained renewed interest as the security foundations for several post-quantum schemes, including LESS. A recent paper has introduced the use of the Schur product to solve PEP, identifying many new easy-to-solve instances. In this paper, we extend this result to LEP. In particular, we generalize the approach and rely on the more general notion of power codes. Combining it with Frobenius automorphisms and Hermitian hulls, we identify many classes of easy LEP instances. To the best of our knowledge, this is the first work exploiting algebraic weaknesses for LEP. Finally we show an improved reduction to PEP whenever the coefficients of the monomial matrix are in a subgroup of the multiplicative group of the finite field.

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 extends the Schur-product attack on the Permutation Equivalence Problem (PEP) to the Linear Equivalence Problem (LEP) by replacing codes with their power codes, then applying Frobenius automorphisms to produce Hermitian hulls whose low dimension is claimed to collapse the isometry search. It further gives an improved reduction from LEP to PEP when the monomial-matrix coefficients lie in a suitable subgroup of the multiplicative group of the finite field. The central claim is that these constructions yield many new families of easy LEP instances, the first such algebraic attack for LEP.

Significance. If the hull-dimension drop and subgroup conditions hold, the work is significant: it supplies the first explicit algebraic method for identifying easy LEP instances, generalizing the recent PEP results and directly affecting the concrete security of code-based post-quantum schemes such as LESS. The algebraic approach (power codes + Frobenius + Hermitian hulls) is a natural and potentially reusable extension of existing techniques.

major comments (2)
  1. [§4] §4 (Hermitian-hull construction): the claim that the hull dimension falls below the generic bound min(k,n-k) after Frobenius action is asserted without a closed-form expression in terms of q, n, k and the power exponent, nor any concrete small-field example (e.g., q=4, n=8, k=4, exponent=2) that measures the actual dimension drop.
  2. [final section] Final section (improved PEP reduction): the subgroup condition on monomial coefficients is stated, but the paper does not exhibit the resulting subgroup order or show that it produces new families beyond the already-known permutation cases; the reduction therefore remains formally correct but its practical enlargement of the easy-instance set is not quantified.
minor comments (2)
  1. Notation for the power-code exponent and the Frobenius action should be introduced once and used consistently; several paragraphs reuse the same symbol for distinct objects.
  2. [introduction] The abstract states the result is 'the first work exploiting algebraic weaknesses for LEP,' but the introduction should cite the precise prior PEP papers to make the novelty claim precise.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive suggestions. We address each major comment below. Where revisions strengthen the presentation we have incorporated them; we maintain that the core claims hold but agree that additional concrete illustration improves clarity.

read point-by-point responses

  1. Referee: §4 (Hermitian-hull construction): the claim that the hull dimension falls below the generic bound min(k,n-k) after Frobenius action is asserted without a closed-form expression in terms of q, n, k and the power exponent, nor any concrete small-field example (e.g., q=4, n=8, k=4, exponent=2) that measures the actual dimension drop.

    Authors: A general closed-form expression for the hull dimension after the combined power-code and Frobenius action is not available in elementary terms because the dimension drop depends on the specific arithmetic relations between the support of the power code and the fixed field of the automorphism; deriving a uniform formula would require case-by-case analysis of the minimal polynomial of the Frobenius action on the code. We therefore illustrate the phenomenon by direct computation. In the revised manuscript we add an explicit small-field example with q=4, n=8, k=4 and exponent 2, showing that the Hermitian hull dimension drops to 1, strictly below min(k,n-k)=4. This concrete verification supports the claim for the families under consideration while acknowledging that a universal closed-form remains open. revision: yes

  2. Referee: Final section (improved PEP reduction): the subgroup condition on monomial coefficients is stated, but the paper does not exhibit the resulting subgroup order or show that it produces new families beyond the already-known permutation cases; the reduction therefore remains formally correct but its practical enlargement of the easy-instance set is not quantified.

    Authors: The subgroup condition enlarges the set of monomial matrices to which the reduction applies precisely when the diagonal entries lie in a proper subgroup G of F_q^* with |G|>1. In the revision we explicitly compute the orders of the relevant subgroups for representative field sizes (e.g., the quadratic residues when q≡1 mod 4) and exhibit two infinite families of monomial equivalences whose coefficients lie in such subgroups but are not permutations. These families are distinct from the pure permutation case and therefore enlarge the known easy LEP instances. While a complete asymptotic count over all parameters is outside the paper’s scope, the added examples quantify the enlargement for concrete parameter regimes. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the algebraic derivation

full rationale

The paper extends the Schur-product attack on PEP to LEP by replacing codes with their power codes and combining Frobenius automorphisms with Hermitian hulls to produce instances where the isometry search reduces. The classification of these instances as 'easy' follows from the algebraic consequence that the hull dimension drops for chosen exponents and fields, rather than being defined in terms of the isometry itself. No equation or step reduces by construction to a fitted parameter or self-referential input; the monomial-subgroup condition for the improved PEP reduction is an explicit additional hypothesis, not a tautology. The cited prior Schur-product work is treated as external input, and the derivation remains self-contained against the stated algebraic assumptions without load-bearing self-citation chains or ansatz smuggling.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central claim rests on the algebraic properties of power codes, Frobenius automorphisms, and Hermitian hulls over finite fields. No explicit free parameters, invented entities, or non-standard axioms are visible in the abstract.

pith-pipeline@v0.9.0 · 5501 in / 1134 out tokens · 26981 ms · 2026-05-15T00:34:58.731867+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Hol- low LWE: A New Spin

    Martin R. Albrecht, Benjamin Benˇ cina, and Russell W. F. Lai. “Hol- low LWE: A New Spin”. In:Advances in Cryptology – EUROCRYPT

    work page

  2. [2]

    by Serge Fehr and Pierre-Alain Fouque

    Ed. by Serge Fehr and Pierre-Alain Fouque. Cham: Springer Nature Switzerland, 2025, pp. 363–392.isbn: 978-3-031-91101-9

    work page 2025

  3. [3]

    SPECK: Signatures from Permu- tation Equivalence of Codes and Kernels

    Marco Baldi, Michele Battagliola, Rahmi El Mechri, Paolo Santini, Ric- cardo Schiavoni, and Davide De Zuane. “SPECK: Signatures from Permu- tation Equivalence of Codes and Kernels”. In:Cryptology ePrint Archive (2025)

    work page 2025

  4. [4]

    Permutation code equivalence is not harder than graph isomorphism when hulls are trivial

    Magali Bardet, Ayoub Otmani, and Mohamed Saeed-Taha. “Permutation code equivalence is not harder than graph isomorphism when hulls are trivial”. In:2019 IEEE International Symposium on Information Theory (ISIT). IEEE. 2019, pp. 2464–2468. 12

    work page 2019

  5. [5]

    Advanced signature functionalities from the code equivalence problem

    Alessandro Barenghi, Jean-Fran¸ cois Biasse, Tran Ngo, Edoardo Persichetti, and Paolo Santini. “Advanced signature functionalities from the code equivalence problem”. In:International Journal of Computer Mathemat- ics: Computer Systems Theory7.2 (2022), pp. 112–128

    work page 2022

  6. [6]

    VOLE-in- the-Head Signatures Based on the Linear Code Equivalence Problem

    Michele Battagliola, Laura Mattiuz, and Alessio Meneghetti. “VOLE-in- the-Head Signatures Based on the Linear Code Equivalence Problem”. In: Cryptology ePrint Archive(2025)

    work page 2025

  7. [7]

    Cryptology ePrint Archive, Paper 2025/1017

    Michele Battagliola, Rocco Mora, and Paolo Santini.Using the Schur Product to Solve the Code Equivalence Problem. Cryptology ePrint Archive, Paper 2025/1017. 2025.url:https://eprint.iacr.org/2025/1017

    work page 2025

  8. [8]

    Not enough LESS: an improved algorithm for solving code equivalence problems overF q

    Ward Beullens. “Not enough LESS: an improved algorithm for solving code equivalence problems overF q”. In:International Conference on Se- lected Areas in Cryptography. Springer. 2020, pp. 387–403

    work page 2020

  9. [9]

    LESS is more: code-based signatures without syndromes

    Jean-Fran¸ cois Biasse, Giacomo Micheli, Edoardo Persichetti, and Paolo Santini. “LESS is more: code-based signatures without syndromes”. In: International Conference on Cryptology in Africa. Springer. 2020, pp. 45– 65

    work page 2020

  10. [10]

    Two Is All It Takes: Asymptotic and Concrete Improvements for Solving Code Equivalence

    Alessandro Budroni, Andre Esser, Ermes Franch, and Andrea Natale. “Two Is All It Takes: Asymptotic and Concrete Improvements for Solving Code Equivalence”. In:Cryptology ePrint Archive(2025)

    work page 2025

  11. [11]

    On linear equiv- alence, canonical forms, and digital signatures

    Tung Chou, Edoardo Persichetti, and Paolo Santini. “On linear equiv- alence, canonical forms, and digital signatures”. In:Designs, Codes and Cryptography(2025), pp. 1–43

    work page 2025

  12. [12]

    Tanuki: New Frameworks for (Concurrently Se- cure) Blind Signatures from Post-Quantum Group Actions

    Lucjan Hanzlik, Yi-Fu Lai, Marzio Mula, Eugenio Paracucchi, Daniel Sla- manig, and Gang Tang. “Tanuki: New Frameworks for (Concurrently Se- cure) Blind Signatures from Post-Quantum Group Actions”. In:Inter- national Conference on the Theory and Application of Cryptology and Information Security. Springer. 2025, pp. 35–69

    work page 2025

  13. [13]

    Cary Huffman and Vera Pless.Fundamentals of Error-Correcting Codes

    W. Cary Huffman and Vera Pless.Fundamentals of Error-Correcting Codes. Cambridge University Press, 2003

    work page 2003

  14. [14]

    An improved algorithm for code equivalence

    Julian Nowakowski. “An improved algorithm for code equivalence”. In: International Conference on Post-Quantum Cryptography. Springer. 2025, pp. 71–103

    work page 2025

  15. [15]

    Counting Abelian Squares

    LB Richmond and Jeffrey Shallit. “Counting Abelian Squares”. In:the electronic journal of combinatorics16.R72 (2009), p. 1

    work page 2009

  16. [16]

    Algebraic approach for code equivalence

    Mohamed Ahmed Saeed. “Algebraic approach for code equivalence”. PhD thesis. Normandie Universit´ e; University of Khartoum, 2017

    work page 2017

  17. [17]

    Finding the permutation between equivalent linear codes: The support splitting algorithm

    Nicolas Sendrier. “Finding the permutation between equivalent linear codes: The support splitting algorithm”. In:IEEE Transactions on Information Theory46.4 (2000), pp. 1193–1203. 13

    work page 2000

  18. [18]

    On the Dimension of the Hull

    Nicolas Sendrier. “On the Dimension of the Hull”. In:SIAM Journal on Discrete Mathematics10.2 (1997), pp. 282–293.url:https://doi.org/ 10.1137/S0895480195294027

    work page doi:10.1137/s0895480195294027 1997

  19. [19]

    How easy is code equivalence overF q?

    Nicolas Sendrier and Dimitrios E Simos. “How easy is code equivalence overF q?” In:International Workshop on Coding and Cryptography-WCC

    work page

  20. [20]

    2013.url:https://inria.hal.science/hal-00790861/document

    work page 2013

  21. [21]

    The hardness of code equivalence overF q and its application to code-based cryptography

    Nicolas Sendrier and Dimitris E Simos. “The hardness of code equivalence overF q and its application to code-based cryptography”. In:International Workshop on Post-Quantum Cryptography. Springer. 2013, pp. 203–216. 14

    work page 2013