Analysis and Decoding of Linear Lee-Metric Codes with Application to Code-Based Cryptography

Kurzfassung

Lee-metric codes are defined over integer residue rings endowed with the Lee metric. Even though the metric is one of the oldest metric considered in coding-theroy and has interesting applications in, for instance, DNA storage and code-based cryptography, it received relatively few attentions compared to other distances like the Hamming metric or the rank metric. Hence, codes in the Lee metric are still less studied than codes in other metrics. Recently, the interest in the Lee metric increased due to its similarities with the Euclidean norm used in lattice-based cryptosystem. Additionally, it is a promising metric to reduce the key sizes or signature sizes in code-based cryptosystem. However, basic coding-theoretic concepts, such as a tight Singleton-like bound or the construction of optimal codes, are still open problems. Thus, in this thesis we focus on some open problems in the Lee metric and Lee-metric codes. Firstly, we introduce generalized weights for the Lee metric in different settings by adapting the existing theory for the Hamming metric over finite rings. We discuss their utility and derive new Singleton-like bounds in the Lee metric. Eventually, we abandon the classical idea of generalized weights and introduce generalized distances based on the algebraic structure of integer residue rings. This allows us to provide a novel and improved Singleton-like bound in the Lee metric over integer residue rings. For all the bounds we discuss the density of their optimal codes. Originally, the Lee metric has been introduced over a $q$-ary alphabet to cope with phase shift modulation. We consider two channel models in the Lee metric. The first is a memoryless channel matching to the Lee metric under the decoding rule ``decode to the nearest codeword''. The second model is a block-wise channel introducing an error of fixed Lee weight, motivated by code-based cryptography where errors of fixed weight are added intentionally. We show that both channels coincide in the limit of large block length, meaning that their marginal distributions match. This distribution enables to provide bounds on the asymptotic growth rate of the surface and volume spectrum of spheres and balls in the Lee metric, and to derive bounds on the block error probability of the two channel models in terms of random coding union bounds. As vectors of fixed Lee weight are also of interest to cryptographic applications, we discuss the problem of scalar multiplication in the Lee metric in the asymptotic regime and in a finite-length setting. The Lee weight of a vector may be increased or decreased by the product with a nontrivial scalar. From a cryptographic view point this problem is interesting, since an attacker may be able to reduce the weight of the error and hence reduce the complexity of the underlying problem. The construction of a vector with constant Lee weight using integer partitions is analyzed and an efficient method for drawing vectors of constant Lee weight uniformly at random from the set of all such vectors is given. We then focus on regular LDPC code families defined over integer residue rings and analyze their performance with respect to the Lee metric. We determine the expected Lee weight enumerator for a random code in fixed regular LDPC code ensemble and analyze its asymptotic growth rate. This allows us to estimate the expected decoding error probability. Eventually, we estimate the error-correction performance of selected LDPC code families under belief propagation decoding and symbol message passing decoding and compare the performances. The thesis is concluded with an application of the results derived to code-based cryptography. Namely, we apply the marginal distribution to improve the yet known fastest Lee-information set decoding algorithm.