Ring ISD - On the security of not yet implemented schemes

Abstract

Decoding a random linear code is a computationally hard problem and is considered as one of the main problems in coding theory. Because of this, it is the basis of many code-based cryptosystems. One of the families of decoders used to solve this problem is Information Set Decoding (ISD), which is a set of generic algorithms that can be applied to decode any input code. An ISD algorithm can recover the message from a corrupted codeword or identify the error vector. ISD algorithms still represent the main method for decoding random linear codes in the Hamming metric, especially when the problem has only a small number of solutions.

In this talk, we discuss the behavior of ISD algorithms in the not-so-well-studied regimes of linear codes over the integer residue ring  equipped with Hamming metric. In this framework, ISD algorithms can adapt to the underlying structure and exploit it to their advantage to obtain significantly lower complexity. In particular, projecting the instance of the problem over the base field and then tracing it back to a solution over is more efficient than applying ISD to the original instance directly.