The problem of finding an error vector with fixed Hamming weight given a parity check matrix of a linear code and a syndrome vector is one of the oldest and most representative problems in code-based cryptography. From public-key encryption schemes to digital signatures, the Syndrome Decoding Problem (SDP) has become a common denominator.
Recently, a slight modification of this well-studied problem, combined with a new technique in laser fault injections, enabled efficient message recovery attacks against the classic McEliece cryptosystem(Message Recovery Attack)
The integer syndrome decoding problem is one of the topics we focus our interest. More exactly, we are looking for two types of algorithms for this problem: exact (with presumably exponential time complexity) and probabilistic (with polynomial time complexity).
Algorithms for Integer Syndrome Decoding Problem
We have proposed three different algorithms for solving this problem: 1. combinatorial (exponential time complexity in the worst case), 2. based on Integer Linear Programming (no theoretical evidence of the complexity so far), 3. ISD-Scode Decoder (polynomial time complexity).
For the best solution (ISD-Score Decoder) we have provided theoretical evidence of its complexity and practical simulations, using implementations for small to large set of parameters. The algorithm not only that retrieves a solution to the Integer Syndrome Decoding Problem but it manages to find it even in a noisy scenario. This is the case when hybrid attacks are performed and a noisy estimation of the integer syndrome is computed. The results (in a short 5 page article) were accepted for presentation and publication at IEEE ITW 2022.