Information Set Decoding for Ring-Linear Code

Giulia Cavicchioni; Alessio Meneghetti; Giovanni Tognolini

Paper 2024/1679

Information Set Decoding for Ring-Linear Code

Giulia Cavicchioni, University of Trento

Alessio Meneghetti, University of Trento

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 Problem 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 show that it is possible to leverage the ring structure to construct more efficient decoding algorithms than those obtained by simply adapting ISD. In particular, we describe a framework that can be applied to any additive metric including Hamming and Lee, and that can be adapted to the case of the rank metric, providing algorithms to solve the two aforementioned problems, along with their average computational costs.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Ring-linear codes Information Set Decoding Hamming metric Lee metric Rank metric
Contact author(s): giulia cavicchioni @ unitn it
alessio meneghetti @ unitn it
giovanni tognolini @ unitn it
History: 2024-10-18: approved; 2024-10-16: received; See all versions
Short URL: https://ia.cr/2024/1679
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1679,
      author = {Giulia Cavicchioni and Alessio Meneghetti and Giovanni Tognolini},
      title = {Information Set Decoding for Ring-Linear Code},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1679},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1679}
}