On Codes from Split Metacyclic Groups
Kirill Vedenev · 2025
Read On Codes from Split Metacyclic Groups by Kirill Vedenev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-11960.txt.
Introduction
Kirill Vedenev studies in 2025 codes built from a class of non-abelian groups called split metacyclic groups. Codes from groups turn algebra into rules for sending data with less error. The work gives a full account of this group code family.
Vedenev breaks the group algebra into clear parts when the field size fits the group size. From that split, the codes can be read as joined codes with simple inner parts and skewed outer parts. Bounds on the least gap between code words are proved. The joined form also lets a partial key attack work on some code based locks.
Catalog record
| CREATOR | Kirill Vedenev |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-11960
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Codes from Split Metacyclic Groups Kirill Vedenev Abstract The paper presents a comprehensive study of group codes from non-abelian split metacyclic group algebras. We derive an explicit Wedderburn-like decomposition of finite split metacyclic group algebras over fields with characteristic coprime to the group order. Utilizing this decomposition, we develop a systematic theory of metacyclic codes, providing their algebraic description and proving that they can be viewed as generalized concatenated codes with cyclic inner codes and skew quasi-cyclic outer codes. We establish bounds on the minimum distance of metacyclic codes and investigate the class of induced codes. Furthermore, we show the feasibility of constructing a partial key-recovery attack against certain McEliece-type cryptosystems based on metacyclic codes by exploiting their generalized concatenated structure. keywords Group codes, Metacyclic groups, Wedderburn decomposition, Generalized concatenated codes, Induced codes, Code-based cryptography 1 Introduction Let G be a finite group and R be a ring with unity. The set RG of all formal linear combinations of the form \sum_{g\in G}\lambda_{g}g , where \lambda_{g}\in R , equipped with the following operations of addition, multiplication, and multiplication by a scalar: \left(\sum_{g\in G}\lambda_{g}g\right)+\left(\sum_{g\in G}\mu_{g}g\right)=\sum_{g\in g}(\lambda_{g}+\mu_{g})g, \left(\sum_{g\in G}\lambda_{g}g\right)\left(\sum_{g\in G}\mu_{g}g\right)=\sum_{g\in g}\Bigg(\sum_{\begin{subarray}{c}h,h^{\prime}\in G\\ hh^{\prime}=g\end{subarray}}\lambda_{h}\mu_{h^{\prime}}\Bigg)g=\sum_{g\in G}\left(\sum_{h\in G}\lambda_{h}\mu_{h^{-1}g}\right)g, \mu\left(\sum_{g\in G}\lambda_{g}g\right)=\sum_{g\in G}(\mu\lambda_{g})g,\quad\left(\sum_{g\in G}\lambda_{g}g\right)\mu=\sum_{g\in G}(\lambda_{g}\mu)g, is called the group ring of G over R . If R is commutative, then RG is also called the group algebra of G over R ( Milies and Sehgal, 2002 , §3.2) . There is a natural embedding of G into RG given by x\mapsto\sum_{g\in G}\lambda_{g}g , where \lambda_{x}=1 and \lambda_{g}=0 for all g\neq x . Similarly, there is a natural embedding of R into RG via r\mapsto re . So, both G and R can be regarded as subsets of RG . Given an element u=\sum_{g\in G}u_{g}g\in RG , the support of u is defined by \operatorname{supp}(u)=\left\{g\in G\mid u_{g}\neq 0\right\}, and the Hamming weight of u is defined by \operatorname{wt}\left(u\right)=|\operatorname{supp}(u)| . The Hamming distance on RG is given by \operatorname{dist}_{H}(u,v)=\operatorname{wt}\left(u-v\right) for u,v\in RG . For a finite field \mathds{F}_{q} of cardinality q and a finite group G , any left (respectively, right) ideal C of the group ring \mathds{F}_{q}G endowed with the Hamming distance \operatorname{dist}_{H} is called a left (resp. right) group code or a left (resp. right) G -code Willems (2021) . Note that the anti-automorphism of \mathds{F}_{q}G given by u=\sum_{g\in G}u_{g}g\mapsto u^{*}=\sum_{g\in G}u_{g^{-1}}g (1) (see ( Milies and Sehgal, 2002 , Proposition 3.2.11) ) establishes a one-to-one correspondence between left and right G -codes. In other words, if C is a left (resp. right) G -code, then C^{*}=\{c^{*}\mid c\in C\} is a right (resp. left) G -code. Therefore, we will mainly focus on left G -codes, which will be simply referred to as G -codes unless otherwise specified. The group codes, introduced independently by S. Berman in Berman (1969) and F. MacWilliams in MacWilliams (1970) , form a powerful class of linear codes that possess many desirable properties, including efficient encoding and decoding, as well as the applicability of algebraic methods for studying them. Abelian codes, i.e., codes from abelian group algebras, have been studied in some depth, while there are not many systematic results known about non-abelian codes. Non-abelian codes are particularly interesting due to their possible applications in code-based cryptography, since their complex algebraic structure was conjectured to improve the security of code-based cryptosystems and reduce public key sizes Deundyak and Kosolapov (2015) ; Deundyak and Kosolapov (2016) . Being the simplest class of non-abelian groups, split metacyclic groups G_{n,m,r} , which are defined by the following presentation G_{n,m,r}=\left<a,b\mid a^{n}=b^{m}=e,ba=a^{r}b\right>, where r^{m}\equiv 1\ (\operatorname{mod}\ n) , are natural choice for studying non-abelian codes. As demonstrated in Vedenev and Deundyak (2018) ; Vedenev and Deundyak (2019) ; Vedenev and Deundyak (2020a) ; Vedenev and Deundyak (2020b) in the case of dihedral groups, the Wedderburn decomposition of a group algebra into a direct sum of matrix algebras turns out to be a very powerful and convenient tool for studying group codes. However, the problem of explicitly constructing such decompositions is very non-trivial. Contribution. The contribution of this paper is twofold. First, an explicit Wedderburn-like decomposition of finite split metacyclic group algebras is obtained. Second, a systematic theory of split metacyclic codes is developed by leveraging this decomposition. Specifically, it is proved that metacyclic codes can be viewed as generalized concatenated codes, with inner codes being cyclic codes and outer codes being skew quasi-cyclic codes. In addition, the class of induced codes is studied, and estimates of the main parameters of metacyclic codes are obtained. Finally, the possibility of building a partial key-recovery attack against certain metacyclic code-based McEliece-type cryptosystems is demonstrated. Organization. Section 2 provides the necessary preliminaries. In Section 3 , a decomposition for finite split metacyclic group algebras in the case where \gcd(q,n)=1 is obtained. In Section 4 , the algebraic description of metacyclic codes is given, and their concatenated structure is studied. Additionally, these results are used to derive a lower bound on the minimum distance of metacyclic codes and to build partial key-recovery attacks against cryptosystems based on some metacyclic codes. Section 5 provides an algebraic description of induced codes and derives a lower bound on the minimum distance of metacyclic codes by leveraging induced codes. Finally, Section 6 concludes the paper. Prior and Related Works. In 1994, R. Sabin Sabin (1994) showed that some quasi-cyclic codes can be viewed as ideals of metacyclic group algebras and discovered that several such codes have minimum distances equal to those of the best-known linear codes. In 1995, R. Sabin and S. Lomonaco Sabin and Lomonaco (1995) proved that central codes, i.e., two-sided ideals, from semisimple metacyclic group algebras are combinatorially equivalent to abelian codes, and provided several examples of good non-central codes obtained by leveraging group representations. Additionally, they described an algorithm for finding irreducible representations in the case when the ambient field \mathds{F}_{q} contains all n -th roots of unity. In 2016, S. Assuena and C.P. Miles Assuena and Milies (2016) considered semisimple non-abelian metacyclic group algebras and described their primitive central idempotents in the case when the order of G equals p^{m}l^{n} , where p and l are different prime numbers. In their recent works Assuena and Milies (2019) ; Assuena (2020) , S. Assuena and C.P. Miles proposed constructions of some non-central codes from metacyclic group algebras by leveraging idempotents derived from subgroups, with parameters of some of those codes matching the best known linear codes. In 2007, O. Broche and A. del Rio Broche and Del Río (2007) proposed a computational method for describing the Wedderburn decomposition and the primitive central idempotents of a semisimple finite group algebra of an abelian-by-supersolvable group G from certain pairs of subgroups of G . Building upon this work, in 2014, G. Olteanu and V. Gelder Olteanu and Van Gelder (2014) proposed algorithms to construct minimal left group codes and showed that their main result can be applied to metacyclic groups of the form G_{q^{m},p^{n},r}=C_{q^{m}}\leftthreetimes C_{p^{n}} with C_{p^{n}} acting faithfully on C_{q^{m}} , where p and q are different primes and the field size s is coprime to p and q . In 2015, F. E. Brochero Martinez Brochero Martinez (2015) obtained an explicit Wedderburn decomposition of the semisimple dihedral group algebras \mathds{F}_{q}D_{2n} , where