Codes over Galois Rings and Their Cryptographic Applications

Abstract

In 1948, Claude Shannon introduced coding theory. From a mathematical point of view, linear codes are submodules in which a metric is defined. Some examples of these are Goppa codes and Gabidulin codes, originally defined over finite fields, hence being vector subspaces with a specific metric. When considering codes over rings, however, the amount of codes available in the bibliography is considerably more reduced. Some examples of these are Kerdock and Preparata codes, which can be seen as codes over the quaternary ring. In the first part of this PhD thesis, we generalise both of Goppa and Gabidulin codes to Galois rings, and study some of their properties and relations to the originals. One of the most remarkable applications of coding theory is the McEliece cryptosystem from 1978, which exploits the hardness of the mathematical problem of, given an element in a vector space, finding its closest vector belonging to a given random linear subspace. In the final part of this thesis, we study the security of a ring version of the same cryptosystem with the previously mentioned codes in its core. This security relies mainly in two points: the computational hardness of a ring version of the mathematical problem described above, and the problem of distinguishing the given submodule from a randomly generated one. We prove that the former remains hard, while the latter fails for some of the codes presented in the first part. This cryptosystem (in its binary version) is also known for being one ofthe few classical cryptographic schemes resisting attacks from a quantum computer. This has led us to propose a quantum attack on the cryptosystem by modelling the previously mentioned mathematical problem as an optimisation problem.