Generic Decoding of Ring-Linear Codes

Decoding a random linear code is a computationally hard problem at the core of code-based cryptography, and Information Set Decoding (ISD) remains the primary generic technique for tackling it. Although coding-theoretic problems over finite rings are generally considered more complex than their counterparts over finite fields, we show that generic decoding is a notable exception. In this talk, we explore the behavior of ISD algorithms in the less-studied setting of codes over the integer residue ring $\mathbb{Z}/p^s\mathbb{Z}$, equipped with the Hamming, Lee, and Rank metrics. In this framework, ISD algorithms can leverage the underlying algebraic structure to significantly outperform a direct adaptation of ISD to rings.