# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell  
The ISD algorithm introduced by [PERSON] and [PERSON] in Lee and Brickell (2017) starts with the same initial operations as in [PERSON]'s, i.e., the computation of the Reduced Row Echelon Form (RREF) of \(\tilde{H}\) and the derivation of the corresponding syndrome \(\tilde{s}\). However, [PERSON] and [PERSON] improved [PERSON]'s original idea by allowing \(p\) positions in the \(k\) selected in the error vector to be error-affected. These \(p\) remaining error positions are guessed. To verify the guess, [PERSON] and [PERSON] exploit the identity \([V\;I_{r}]\;\widehat{e}^{T}=\tilde{s}\), where is split in two parts, \(\widehat{e}=[\widehat{e}_{1}\widehat{e}_{2}]\), with \(\widehat{e}_{1}\) being \(k\) bit long and with weight \(p\), and \(\widehat{e}_{2}\) being \(r\) bits long and with weight \(t-p\). The identity is rewritten as \(V\widehat{e}_{1}^{T}+I_{r}\widehat{e}_{2}^{T}=V\widehat{e}_{1}^{T}+\widehat{e }_{2}^{T}=\bar{s}\), from which follows the fact that \(V\widehat{e}_{1}^{T}+\bar{s}=\widehat{e}_{2}^{T}\) must have weight \(t-p\). Indeed, this condition is employed by the algorithm to check if the guess of \(p\) positions is correct. The procedure is summarized in Algorithm 2. ```
Input:\(s\): an \(r\)-bit long syndrome (column vector) \(H\): an \(r\times n\) binary parity-check matrix \(t\): the weight of the error vector to be recovered Output:\(e\): an \(n\)-bit binary row error vector s.t. \(He^{T}=s\), with weight\((e)=t\) Data:\(P\): an \(n\times n\) permutation matrix \(\widehat{e}=eP\): the error vector permuted by \



i.e., \(\binom{k}{p}\) as they constitute the body of the loop at Lines 4-9. Note that, in a practical implementation where the value of \(p\) is fixed, it is possible to avoid \(\mathrm{C}_{\mathrm{IntToComb}}\) altogether, specializing the algorithm with a \(p\)-deep loop nest to enumerate all the weight \(p\), length \(k\) binary vectors. Adapting [PERSON]'s Information Set Decoding (ISD) allows employing substantially the same algorithm to solve the Codeword Finding Problem (CFP), given a parity matrix \(H\) as the representation of the code where a weight \(w\) codeword \(c\) should be found. The line of reasoning to employ [PERSON]'s Information Set Decoding (ISD) to solve the Codeword Finding Problem (CFP) is to note that, by definition, for any codeword \(c\) of the code represented by \(H\) we have that \(Hc^{T}=0_{1\times r}\), i.e., a codeword multiplied by the parity check matrix yields a null syndrome. As a consequence, we have that \(0_{1\times r}=Hc^{T}=HPP^{T}c^{T}=\hat{H}P^{T}c^{T}=\hat{H}\hat{c}^{T}=V\hat{c} _{1}^{T}+\hat{c}_{2}^{T}\). This implies that \(V\hat{c}_{1}^{T}=\hat{c}_{2}^{T}\), which can be exploited as an alternative stopping condition to the one of Algorithm 2, yielding in turn Algorithm 3. The only remaining difference between the Syndrome Decoding Problem (SDP) solving [PERSON]'s ISD and the Codeword Finding Problem (CFP) is represented by the ISextract primitive, which no longer needs to compute a transformed syndrome \(s=Us\) as it is null. We thus have a small reduction in \(\mathrm{C}_{\mathrm{IS}}(n,r)\), which becomes \(\mathrm{C}_{\mathrm{IS}}(n,r)=\frac{1}{\prod_{c=1}^{r}(1-2^{-i})}\)\(\mathrm{C}_{\mathrm{REFE}}(n,r)+n\), losing an additive \(r^{2}\) term. We note that such a reduction is expected to have little impact in practice as the dominant portion of the ISextract function is represented by the Reduced Row Echelon Form (RREF) computation. This in turn implies that solving the Syndrome Decoding Problem (SDP) on a code \(\mathcal{C}\) has practically the same complexity of finding a codeword with weight \(w=t\) in the same code. Therefore, finding low-weight codewords in the code defined by a Niederreiter cryptosystem public key \(H_{pub}\) has an effort comparable to the one of performing syndrome decoding assuming an error with the same weight as the codeword to be found.