The Power of Power Codes: New Classes of Easy Instances for the Linear Equivalence Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918464739868672 |
|---|---|
| author | Battagliola, Michele Horlemann, Anna-Lena Mazumder, Abhinaba Mora, Rocco Santini, Paolo Schaller, Michael Weger, Violetta |
| author_facet | Battagliola, Michele Horlemann, Anna-Lena Mazumder, Abhinaba Mora, Rocco Santini, Paolo Schaller, Michael Weger, Violetta |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23230 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Power of Power Codes: New Classes of Easy Instances for the Linear Equivalence Problem Battagliola, Michele Horlemann, Anna-Lena Mazumder, Abhinaba Mora, Rocco Santini, Paolo Schaller, Michael Weger, Violetta Cryptography and Security Information Theory 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. |
| title | The Power of Power Codes: New Classes of Easy Instances for the Linear Equivalence Problem |
| topic | Cryptography and Security Information Theory |
| url | https://arxiv.org/abs/2603.23230 |