Paper 2024/1679

Information Set Decoding for Ring-Linear Codes

Abstract

Information Set Decoding (ISD) algorithms currently offer the most powerful tool to solve the two archetypal problems of coding theory, namely the codeword finding roblem and the syndrome decoding problem. Traditionally, ISD have primarily been studied for linear codes over finite fields, equipped with the Hamming metric. However, recently, other possibilities have also been explored. These algorithms have been adapted to different ambient spaces and metrics, such as the rank metric or the Lee metric over $\mathbb{Z}_m$. In this paper, we propose a general framework for decoding ring-linear codes that exploits the underlying ring structure to improve traditional approaches. The core idea is to project the decoding instance onto a smaller alphabet, which may enable more efficient decoding algorithms. Our framework is compatible with any coordinate-additive metric, including Hamming and Lee, and can also be adapted to the rank metric. However, we show that the effectiveness of this approach strongly depends on the chosen metric. We illustrate how this framework can be leveraged to design decoding algorithms for the two aforementioned problems in Hamming, rank, and Lee metrics, along with their range of effectiveness. For each case, we provide the average computational complexity of the resulting algorithms.