Paper 2024/1679

Information Set Decoding for Ring-Linear Codes

Giulia Cavicchioni, German Aerospace Center
Alessio Meneghetti, University of Bari Aldo Moro
Giovanni Tognolini, University of Trento
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 . 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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Ring-linear codesInformation Set DecodingHamming metricLee metricRank metric
Contact author(s)
giulia cavicchioni @ dlr de
alessio meneghetti @ uniba it
giovanni tognolini @ unitn it
History
2025-06-16: revised
2024-10-16: received
See all versions
Short URL
https://ia.cr/2024/1679
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1679,
      author = {Giulia Cavicchioni and Alessio Meneghetti and Giovanni Tognolini},
      title = {Information Set Decoding for Ring-Linear Codes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1679},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1679}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.