Joachim Rosenthal

In this paper, we initiate the study of constant-dimension subspace codes restricted to Schubert varieties, which we call Schubert subspace codes. These codes have a very natural geometric description, as objects that we name intersecting sets with respect to a fixed subspace. We provide a geometric construction of the maximum-size constant-dimension subspace codes in some Schubert varieties with the largest possible value for the minimum subspace distance. Finally, we generalize the problem to different values of the minimum distance.

Most low-density parity-check (LDPC) code constructions are considered over finite fields. In this work, we focus on regular LDPC codes over integer residue rings and analyze their performance with respect to the Lee metric. Their error-correction performance is studied over two channel models, in the Lee metric. The first channel model is a discrete memoryless channel, whereas in the second channel model an error vector is drawn uniformly at random from all vectors of a fixed Lee weight. It is known that the two channel laws coincide in the asymptotic regime, meaning that their marginal distributions match. For both channel models, we derive upper bounds on the block error probability in terms of a random coding union bound as well as sphere packing bounds that make use of the marginal distribution of the considered channels. We estimate the decoding error probability of regular LDPC code ensembles over the channels using the marginal distribution and determining the expected Lee weight distribution of a random LDPC code over a finite integer ring. By means of density evolution and finite-length simulations, we estimate the error-correction performance of selected LDPC code ensembles under belief propagation decoding and a low-complexity symbol message passing decoding algorithm and compare the performances. The analysis developed in this paper may serve to design regular low-density parity-check (LDPC) codes over integer residue rings for storage and cryptographic application.

The improvements on quantum technology are threatening our daily cybersecurity, as a capable quantum computer can break all currently employed asymmetric cryptosystems. In preparation for the quantum-era the National Institute of Standards and Technology (NIST) has initiated in 2016 a standardization process for public-key encryption (PKE) schemes, key-encapsulation mechanisms (KEM) and digital signature schemes. In 2023, NIST made an additional call for post-quantum signatures. With this chapter we aim at providing a survey on code-based cryptography, focusing on PKEs and signature schemes. We cover the main frameworks introduced in code-based cryptography and analyze their security assumptions. We provide the mathematical background in a lecture notes style, with the intention of reaching a wider audience.

Maximum-distance separable (MDS) convolutional codes are characterized by the property that their free distance reaches the generalized Singleton bound. In this paper, new criteria to construct MDS convolutional codes are presented. These codes also possess optimal first (reverse) column distances. The new criteria allow to relate the construction of MDS convolutional codes to those of reverse superregular Toeplitz matrices. Moreover, using the new criteria as well as the help of computer search, examples for MDS convolutional codes over small finite fields are given.

This paper investigates the concept of self-dual convolutional codes. We derive the basic properties of this interesting class of codes and we show how some of the techniques to construct self-dual linear block codes generalize to self-dual convolutional codes. As for self-dual linear block codes we are able to give a complete classification for some small parameters.

In this paper, we develop the theory of convolutional codes over finite commutative chain rings. In particular, we focus on maximum distance profile (MDP) convolutional codes and we provide a characterization of these codes, generalizing the one known for fields. Moreover, we relate (reverse) MDP convolutional codes over a finite chain ring with (reverse) MDP convolutional codes over its residue field. Finally, we provide a construction of (reverse) MDP convolutional codes over finite chain rings generalizing the notion of (reverse) superregular matrices.

We study the performance of nonbinary low-density parity-check (LDPC) codes over finite integer rings over two channels that arise from the Lee metric. The first channel is a discrete memory-less channel (DMC) matched to the Lee metric. The second channel adds to each codeword an error vector of constant Lee weight, where the error vector is picked uniformly at random from the set of vectors of constant Lee weight. It is shown that the marginal conditional distributions of the two channels coincide, in the limit of large block length. Random coding union bounds on the block error probability are derived for both channels. Moreover, the performance of selected LDPC code ensembles is analyzed by means of density evolution and finite-length simulations, with belief propagation decoding and with a low-complexity symbol message passing algorithm and it is compared to the derived bounds.

Coding theory where the alphabet is identified with the elements of a ring or a module has become an important research topic over the last 30 years. It has been well established that, with the generalization of the algebraic structure to rings, there is a need to also generalize the underlying metric beyond the usual Hamming weight used in traditional coding theory over finite fields. This paper introduces a generalization of the weight introduced by Shi, Wu and Krotov, called overweight. Additionally, this weight can be seen as a generalization of the Lee weight on the integers modulo 4 and as a generalization of Krotov’s weight over the integers modulo 2^s for any positive integer s. For this weight, we provide a number of well-known bounds, including a Singleton bound, a Plotkin bound, a sphere-packing bound and a Gilbert–Varshamov bound. In addition to the overweight, we also study a well-known metric on finite rings, namely the homogeneous metric, which also extends the Lee metric over the integers modulo 4 and is thus heavily connected to the overweight. We provide a new bound that has been missing in the literature for homogeneous metric, namely the Johnson bound. To prove this bound, we use an upper estimate on the sum of the distances of all distinct codewords that depends only on the length, the average weight and the maximum weight of a codeword. An effective such bound is not known for the overweight.

New constructions for moderate-density parity-check (MDPC) codes using finite geometry are proposed. We design a parity-check matrix for the main family of binary codes as the concatenation of two matrices: the incidence matrix between points and lines of the Desarguesian projective plane and the incidence matrix between points and ovals of a projective bundle. A projective bundle is a special collection of ovals which pairwise meet in a unique point. We determine the minimum distance and the dimension of these codes, and we show that they have a natural quasi-cyclic structure. We consider alternative constructions based on an incidence matrix of a Desarguesian projective plane and compare their error-correction performance with regards to a modification of Gallager’s bit-flipping decoding algorithm. In this setting, our codes have the best possible error-correction performance after one round of bit-flipping decoding given the parameters of the code’s parity-check matrix.