We convert Stern's information set decoding (ISD) algorithm to the ring $ \mathbb{Z}/4 \mathbb{Z} $ equipped with the Lee metric. Moreover, we set up the general framework for a McEliece and a Niederreiter cryptosystem over this ring. The complexity of the ISD algorithm determines the minimum key size in these cryptosystems for a given security level. We show that using Lee metric codes can substantially decrease the key size, compared to Hamming metric codes. In the end we explain how our results can be generalized to other Galois rings $ \mathbb{Z}/p^s\mathbb{Z} $.

In this paper we study the hardness of the syndrome decoding problem over finite rings endowed with the Lee metric. We first prove that the decisional version of the problem is NP-complete, by a reduction from the $ 3 $-dimensional matching problem. Then, we study the complexity of solving the problem, by translating the best known solvers in the Hamming metric over finite fields to the Lee metric over finite rings, as well as proposing some novel solutions. For the analyzed algorithms, we assess the computational complexity in the asymptotic regime and compare it to the corresponding algorithms in the Hamming metric.

We present a code-based public-key cryptosystem, in which we use Reed-Solomon codes over an extension field as secret codes and disguise it by considering its shortened expanded code over the base field. Considering shortened expanded codes provides a safeguard against distinguisher attacks based on the Schur product. Moreover, without using a cyclic or a quasi-cyclic structure we obtain a key size reduction of nearly $ 45 \% $ compared to the classic {McE}liece cryptosystem proposed by Bernstein et al.