# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
Two families of codes which may be vulnerable to such an attack unless the parameters are designed taking into account a Codeword Finding Problem (CFP) ISD are the Low Density Parity Check (LDPC) and Moderate Density Parity Check (MDPC) codes. Indeed, such code families can be represented with a parity check matrix with low-weight rows, and such a low-weight representation can be relied upon to perform efficient decoding, leading to an effective cryptosystem break. Indeed, we now show that, if a code \(\mathcal{C}(n,k,d)\) can be represented by a low-weight parity matrix \(H_{priv}\), the code will contain low weight codewords. Without loss of generality, consider \(k>r\). Moreover, consider \(H_{priv}\) as split in three portions \([A_{I}A_{r}B]\) of size \(r\times(k-r)\), \(r\times r\) and \(r\times r\), respectively, with \(B\) non-singular. We derive the corresponding generator matrix as

\[G= \begin{bmatrix}I_{(k-r)\times(k-r)}&0_{(k-r)\times r}&(B^{-1}A_{I})^{T}\\ 0_{r\times(k-r)}&I_{r\times r}&(B^{-1}A_{r})^{T}\end{bmatrix} \]

and consider the bottom \(r\) rows \([0_{r\times(k-r)}&I_{r\times r}&(B^{-1}A_{r})^{T}]\). Consider the product of such bottom rows by \(B^{T}\), yielding \([0_{r\times(k-r)}&I_{r\times r}&(B^{-1}A_{r})^{T}]B^{T}=[0_{r\times(k-r)}&B^{T} &A_{r}^{T}]\) and note that all the rows of this product are valid codewords, as they are the result of a linear combination of rows of the generator matrix \(G\). Moreover, given that the private parity-check matrix \(H_{priv}\) has low row and column weight by construction, we have that the aforementioned codewords, i.e., the rows of \([0_{r\times(k-r)}&B^{T}&A_{r}^{T}]\), also have a low weight. This fact may thus allow an attacker to perform a Key Recovery Attack (KRA) retrieving the low-weight codewords and rebuilding \(H_{priv}\). A different attack strategy for the same code families is to try and find codewords in the dual code with respect to the one represented by the parity check matrix \(H_{priv}\). Such a code, by definition, sees \(H_{priv}\) as a valid generator matrix, and thus makes it possible to directly reconstruct \(H_{priv}\) solving \(r\) instances of Codeword Finding Problem (CFP) to obtain the \(r\) instances of \(H_{priv}\). Solving the Codeword Finding Problem (CFP) on the dual code implies that Algorithm 3 is called considering the aforementioned \(G\) matrix as a parity check matrix. Thus, if we denote with \(\mathrm{C}_{ISD}(n,r,w)\) the complexity of solving Codeword Finding Problem (CFP) on the code described by \(H_{priv}\), solving the CodewordFinding Problem (CFP) on the dual code, will have a complexity of \(C_{ISD}(n,k,w^{\prime})\), where \(w^{\prime}\) is the weight of the codeword of the dual code. Whether this strategy or the one of solving the Codeword Finding Problem (CFP) on the primal code is more advantageous depending on the code rate and the values of \(w\) and \(w^{\prime}\). ```
Input:\(H\): an \(r\times n\) binary parity-check matrix \(w\): the weight of the codeword to be found Output:\(c\): an \(n\)-bit codeword with weight\((c)=w\) Data:\(P\): an \(n\times n\) permutation matrix \(\widehat{c}=cP\): the error vector permuted by \(P\) \(p\): the weight of the first \(k\) bits of \(\widehat{c},0\leq p\leq w\), \(V\): an \(r\times k\) binary matrix \(V=[v_{0},\dots,v_{k-1}]\)
1 repeat\(\langle P_{r}[V\ I_{r}]\rangle\leftarrow\textsc{ISExtract}(H)\)for\(j\gets 1\)to\(\binom{k}{p}\)do \(\mathcal{I}\leftarrow\textsc{IntegerToCombination}(j)\)// \(\mathcal{I}\) is a set of \(p\) distinct integers in \(\{0,\dots,k-1\}\) ifweight\((\sum_{i\in\mathcal{I}}v_{i})=w-p\)then \(\widehat{c}\leftarrow[0_{1\times k}\ (\sum_{i\in\mathcal{I}}v_{i})^{T}]\)foreach\(i\in\mathcal{I}\)do \(\widehat{c}\leftarrow\widehat{c}+[0_{1\times i}\ 1\ 0_{1\times(r+k-1-i)}]\)break
2 untilweight\((\widehat{c})=w\)return\(\widehat{c}P^{T}\)
```
**Algorithm 3**Codeword finding formulation of [PERSON]'s ISD.