Paper 2024/1679
Information Set Decoding for Ring-Linear Code
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 $\mathbb Z_m$. 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 codesInformation Set DecodingHamming metricLee metricRank 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}
}
