Journal of Algebra and Its Applications

We consider actions of a group or a semigroup on a set, which generalize the setup of discrete logarithm based cryptosystems. Such cryptographic group actions have gained increasing attention recently in the context of isogeny-based cryptography. We introduce generic algorithms for the semigroup action problem and discuss lower and upper bounds. Also, we investigate Pohlig–Hellman type attacks in a general sense. In particular, we consider reductions provided by non-invertible elements in a semigroup, and we deal with subgroups in the case of group actions.

CSIDH is a post-quantum key-exchange scheme based on the action of ideal class groups on supersingular elliptic curves over prime fields. Its short keys and ciphertexts, together with its flexibility as a building block to construct complex cryptographic primitives, has motivated significant research on the efficiency of CSIDH and its resistance against side-channel attacks. In this work, some cutting-edge results from recent contributions are reviewed in a unified treatment, focusing on the mathematical ideas lying behind them rather than on cryptographic and low-level implementation techniques. In particular, we first describe ways to speed up the class-group-action evaluation, which range from the use of different models of elliptic curves to working with different ideal class groups. We then survey some constant-time variants of CSIDH, that make the time and memory consumption during the computation of a public/shared key independent of the secret key. Finally, we examine the computation of the ideal class action when the structure of the ideal class group is known, which is the case for a specific set of CSIDH parameters.

Maximum distance separable convolutional codes are characterized by the property that the free distance reaches the generalized Singleton bound, which makes them optimal for error correction. However, the existing constructions of such codes are available over fields of large size. In this paper, we present the unique construction of MDS convolutional codes of rate $1/2$ and degree $5$ over the field ${𝔽}_{11}$.

In this paper, we give constructions for infinite sequences of finite nonlinear locally recoverable codes ${𝒞}\subseteq {\prod }_{i=1}^N{𝔽}_{q_i}$ over a product of finite fields arising from basis expansions in algebraic number fields. The codes in our sequences have increasing length and size, constant rate, fixed locality, and minimum distance going to infinity.

A hyperbolic code is an evaluation code that improves a Reed–Muller code because the dimension increases while the minimum distance is not penalized. We give necessary and sufficient conditions, based on the basic parameters of the Reed–Muller code, to determine whether a Reed–Muller code coincides with a hyperbolic code. Given a hyperbolic code ${𝒞}$, we find the largest Reed–Muller code contained in ${𝒞}$ and the smallest Reed–Muller code containing ${𝒞}$. We then prove that similar to Reed–Muller and affine Cartesian codes, the $r$th generalized Hamming weight and the $r$th footprint of the hyperbolic code coincide. Unlike for Reed–Muller and affine Cartesian codes, determining the $r$th footprint of a hyperbolic code is still an open problem. We give upper and lower bounds for the $r$th footprint of a hyperbolic code that, sometimes, are sharp.

We introduce a new weight and corresponding metric over finite extension fields for asymmetric error correction. The weight distinguishes between elements from the base field and the ones outside of it, which is motivated by asymmetric quantum codes. We set up the theoretic framework for this weight and metric, including upper and lower bounds, asymptotic behavior of random codes, and we show the existence of an optimal family of codes achieving the Singleton-type upper bound.

In this paper, we study linear codes invariant under a cyclic endomorphism $T,$ called $T$-cyclic codes. Since every cyclic endomorphism can be represented by a cyclic matrix with respect to a given basis, all of these matrices are similar. For simplicity we restrict ourselves to linear codes invariant under the right multiplication by a cyclic matrix $M,$ that we call $M$-cyclic codes, and when $M$ is the companion matrix $C_f$ of a given nonzero polynomial $f(x)$ we call them $f$-cyclic codes. The similarity relation between matrices helps us find connections between $M$-cyclic codes and $f$-cyclic codes, where $f(x)$ is the minimal polynomial of $M.$ The class of $M$-cyclic codes contains cyclic codes and their various generalizations such as constacyclic codes, right and left polycyclic codes, monomial codes, and others. As common in the study of cyclic codes and their generalizations, we make use of the one-to-one correspondence between $M$-cyclic codes and ideals of the polynomial ring $R_{{}_f}:={𝔽}_{{}_q}[x]/〈f(x)〉,$ where $f(x)$ is the minimal polynomial of $M.$ This correspondence leads to some basic characterizations of these codes such as generator and parity check polynomials among others. Next, we study the duality of these codes, where we show that the $b$-dual of an $M$-cyclic code is an $M^{{}^{\ast }}$-cyclic code, where $M^{{}^{\ast }}$ is the adjoint matrix of $M$ with respect to $b,$ and we explore some important results on the duality of these codes. Finally, we give examples as applications of some of the results and we construct some optimal codes.

Of the many families of cryptographic schemes proposed to be post-quantum, a relatively unexplored set of examples comes from group-based cryptography. One of the more central schemes from this area is the so-called Semidirect Product Key Exchange (SDPKE), a generalization of Diffie–Hellman Key Exchange that is plausibly post-quantum. In this report we survey the state of the literature relating to SDPKE, providing a high-level discussion of security, as well as a comprehensive overview of the proposed platforms and the main cryptanalytic ideas relevant to each.

In this paper, we study the relation between the linear subspace of the pseudo-noise (PN)-sequences generated by a primitive polynomial and the simplex code. This family of sequences can be also seen as an Maximum Distance Separable (MDS) ${𝔽}_2$-linear code over ${𝔽}_2^r$. Furthermore, we see how to compute the family of generalized sequences produced by a primitive polynomial by means of a first-order Reed–Muller code.

We introduce and study column cyclic rank metric (CCRM) codes over finite fields. We present natural questions for the existence and characterization of CCRM codes. We completely solve these questions only in the first nontrivial case: The case of the minimum rank distance $d=2$ and the number of rows $m=2$. We also consider linear complementary dual rank metric (LCDRM) codes both in the setting of CCRM codes and in the general setting of rank metric codes. We also ask the natural questions for the existence and characterization of CCRM codes in the subclass of LCDRM codes. We also completely solve these questions for this subclass of LCDRM codes only in the first nontrivial case that $d=2$ and $m=2$. Moreover we extend a characterization of linear complementary dual (LCD) codes of Massey to arbitrary rank metric codes in the general setting.

In this work, we analyze the problem of catastrophicity of encoders of convolutional codes over the Laurent series with coefficients in ${\mathbb{Z}}_{p^r}$, ${\mathbb{Z}}_{p^r}((d))$. Kuijper and Pinto proved in [M. Kuijper and R. Pinto, On minimality of convolutional ring encoders, IEEE Trans. Autom. Control 55(11) (2009) 4890–4897] that, contrary to what happens for codes over $𝔽((d))$, where $𝔽$ is a field, when dealing with ${\mathbb{Z}}_{p^r}((d))$ there are convolutional codes that do not admit non-catastrophic encoders. Nevertheless it was conjectured that any catastrophic convolutional code admits another type of non-catastrophic encoder called $p$-encoder. In this paper we solve this conjecture for a class of $(2,1)$ convolutional codes over ${\mathbb{Z}}_{p^2}$ and show that, in fact, these codes always admit a non-catastrophic p-encoder. We also describe a constructive procedure that allows us to obtain a non-catastrophic $p$-encoder.

We revisit the notion of $r$th generalized column weights for the $j$-truncation of a convolutional code. Taking the limit as $j$ tends to infinity, we define $r$th generalized column weights of a convolutional code. We introduce suitable notions of $j$-equivalence and equivalence, with respect to which generalized column weights are code invariants. We establish some properties of these invariants and compare them with other definitions of generalized distance and weight which appear in the literature.

The construction of (minimal) linear codes from functions has received much attention in the literature. In this paper, we derive several minimal codes from the sets of pre-images of weakly regular plateaued and bent functions over the odd characteristic finite fields. Based on the recent construction method, we obtain six-weight and seven-weight minimal codes from these functions. The Hamming weights in proposed codes are calculated from the character sums of the sets based on the Walsh spectrum of the employed functions, while the weight distributions of the codes are determined from both the sizes of the employed sets and the Walsh distributions of the employed functions.

Using an approach from finite group representation theory we construct quaternary non-projective codes with parameters ${[693,6,480]}_4,{[1386,6,1008]}_4,{[2016,6,1488]}_4$, quaternary projective codes with parameters ${[231,6,160]}_4,{[462,6,336]}_4$ and ${[672,6,496]}_4$ and binary projective codes with parameters ${[693,12,320]}_2,{[1386,12,672]}_2,{[2016,12,992]}_2$ as examples of two-weight codes on which a finite almost quasisimple group of sporadic type acts transitively as permutation groups of automorphisms. In particular, we show that these codes are invariant under the $3$-fold covers $\widehat{3}{\mathrm{\text{M}}}_{22}$ and $\widehat{3}{\mathrm{\text{M}}}_{22}:2$, respectively, of the Mathieu groups ${\mathrm{\text{M}}}_{22}$ and ${\mathrm{\text{M}}}_{22}:2$. Employing a known construction of strongly regular graphs from projective two-weight codes we obtain from the binary projective (respectively, quaternary projective) two-weight codes with parameters those given above, the strongly regular graphs with parameters $(4096,693,152,110),(4096,1386,482,462),$ and $(4096,2016,992,992),$ respectively. The latter graph can be viewed as a $2$-$(4096,2016,992)$-symmetric design with the symmetric difference property whose residual and derived designs with respect to a block give rise to binary self-complementary codes meeting the Grey–Rankin bound with equality.

In [D. R. L. Brown, Plactic key agreement (insecure?), J. Math. Cryptol. 17(1) (2023) 20220010], a novel cryptographic key exchange technique was proposed using the plactic monoid, based on the apparent difficulty of solving division problems in that monoid. Specifically, given elements $c,b$ in the plactic monoid, the problem is to find $q$ for which $qb=c$, given that such a $q$ exists. In this paper, we introduce a metric on the plactic monoid and use it to give a probabilistic algorithm for solving that problem which is fast for parameter values in the range of interest.

The use of codes defined by sparse characteristic matrices, like QC-LDPC and QC-MDPC codes, has become an established solution to design secure and efficient code-based public-key encryption schemes, as also witnessed by the ongoing NIST post-quantum cryptography standardization process. However, similar approaches have been less fortunate in the context of code-based digital signatures, since no secure and efficient signature scheme based on these codes is available to date. The main limitation of previous attempts in this line of research has been the use of sparse signatures, which produces some leakage of information about the private key. In this paper, we propose a new code-based digital signature scheme that overcomes such a problem by publishing signatures that are abnormally dense, rather than sparse. This eliminates the possibility of deducing information from the sparsity of signatures, and follows a recent trend in code-based cryptography exploiting the hardness of the decoding problem for large-weight vectors, instead of its classical version based on small-weight vectors. We focus on one-time use and provide a first parameterization of the new scheme, the main advantages of which are very fast signature generation and verification, and public keys that are not too large for a code-based signature scheme.

There is a non-unital ring $I$ of order 4 defined by generators and relations as $I=〈a,b|2a=2b=0,a^2=b,ab=0〉.$ In this paper, we present special constructions of linear codes over $I$ from the adjacency matrices of two class association schemes. These consist of either Strongly Regular Graphs (SRGs) or Doubly Regular Tournaments (DRTs). We investigate the conditions under which these codes are self-orthogonal, quasi self-dual, or Type IV. As a byproduct of this study, some diophantine relations on the weight of sum of vectors with coefficients in $I$ are derived. Some examples of codes with minimum distance better than that of Type IV codes over unital rings of the same order in modest lengths are given.

In this paper, we define a window code to be the portion of a Spatially-coupled low-density parity check (SC-LDPC) code seen by a single iteration of a windowed decoder. We consider the design of SC-LDPC codes for windowed decoding via optimization of the window code. In particular, because iterative decoding is optimal on codes with cycle-free graph representations, we ask fundamental questions about the construction and parameters of cycle-free window codes. We show that it is possible to have an SC-LDPC code with cycles and with cycle-free window codes. We consider the relationship between the distance of the window code and the distance of the SC-LDPC code. Further, we show that SC-LDPC codes with MDS window codes exist, and all such codes are asymptotically bad. This work gives insight into the tradeoffs between window code parameters and performance of the SC-LDPC code.