Ring ISD - On the security of not yet implemented schemes

Seminario del Dipartimento di Matematica
15 April 2024
Start time 
12:00 pm
PovoZero - Via Sommarive 14, Povo (Trento)
Physics Seminar Room
Dipartimento di Matematica
Target audience: 
University community
UniTrento students
Contact person: 
Dott. Marco Calderini
Contact details: 
Department of Mathematics
Daniele De Bernardini (Phd student in Mathematics)


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 A black background with a black square</p>
<p>Description automatically generated with medium confidence and then tracing it back to a solution over A black background with a black square</p>
<p>Description automatically generated with medium confidence is more efficient than applying ISD to the original instance directly.