# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
The second issue is solved slightly modifying the matching equations as follows

\[V_{\text{up}[\ell]}e_{1}^{(1)} =V_{\text{up}[\ell]}e_{2}^{(1)}+\bar{s}_{\text{up}[\ell]} \rightarrow\] no change \[V_{\text{up}[r_{1}]}e_{1}^{(2)} =V_{\text{up}[r_{1}]}e_{2}^{(2)}+\bar{s}_{\text{up}[r_{1}]} \rightarrow V_{\text{up}[r_{1}]}e_{1}^{(2)}=V_{\text{up}[r_{1}]}e_{2}^{(2)}+ \bar{s}_{\text{up}[r_{1}]}+\text{rnd}_{1}\] \[V_{\text{up}[r_{1}]}e_{3}^{(2)} =V_{\text{up}[r_{1}]}e_{4}^{(2)}+0_{[r_{1}]} \rightarrow V_{\text{up}[r_{1}]}e_{3}^{(2)}=V_{\text{up}[r_{1}]}e_{4}^{(2)}+ \text{rnd}_{1}\] \[V_{\text{up}[r_{2}]}e_{1}^{(3)} =V_{\text{up}[r_{2}]}e_{2}^{(3)}+\bar{s}_{\text{up}[r_{2}]} \rightarrow V_{\text{up}[r_{2}]}e_{1}^{(3)}=V_{\text{up}[r_{2}]}e_{2}^{(3)}+ \bar{s}_{\text{up}[r_{2}]}+\text{rnd}_{1}+\text{rnd}_{2}\] \[V_{\text{up}[r_{2}]}e_{3}^{(3)} =V_{\text{up}[r_{2}]}e_{4}^{(3)}+0_{r_{2}} \rightarrow V_{\text{up}[r_{2}]}e_{3}^{(3)}=V_{\text{up}[r_{2}]}e_{4}^{(3)}+ \text{rnd}_{2}\] \[V_{\text{up}[r_{2}]}e_{5}^{(3)} =V_{\text{up}[r_{2}]}e_{6}^{(3)}+0_{r_{2}} \rightarrow V_{\text{up}[r_{2}]}e_{5}^{(3)}=V_{\text{up}[r_{2}]}e_{5}^{(3)}+ \text{rnd}_{1}+\text{rnd}_{2}\] \[V_{\text{up}[r_{2}]}e_{7}^{(3)} =V_{\text{up}[r_{2}]}e_{8}^{(3)}+0_{r_{2}} \rightarrow V_{\text{up}[r_{2}]}e_{7}^{(3)}=V_{\text{up}[r_{2}]}e_{7}^{(3)}+ \text{rnd}_{2}\]

so that the checks at each level also act in such a fashion that the total sum over \(r_{2},r_{1},\ell\) matches the syndrome already, while retaining the desired randomness. **Proposition 7** (Computational complexity of Algorithm 8). : _Given \(H\), an \(r\times n\) binary parity-check matrix and \(s\), an \(r\)-bit long syndrome (column vector) obtained through \(H\), finding the row error vector \(e\) with length \(n\) and weight \(t\) such that \(s=He^{T}\) with Algorithm 8 requires three additional parameters \(0\leq p\leq t\), \(\ell_{1}\) and \(\ell_{2}\) such that \(\ell_{1}+\ell_{2}=\ell,0\leq\ell\leq(k-p)\)._

_The time complexity of the algorithm is_

\[C_{\text{ISD}}(n,r,t,p,\ell_{1},\ell_{2})=P_{success-BJMM}^{-1}C_{\text{iter}}\]

_where the probability of an iteration to succeed, \(P_{success-BJMM}\), is equal to the one in May-Meurer-Thomae (i.e., \(\frac{(t_{t}^{*})}{(t_{p}^{+})(t_{-p}^{-})}\)), multiplied by a factor which quantifies the fact that it is possible, picking the two disjoint sets over the subsets of \(p_{i}\) positions from the error vector are selected may result in a set which does not contain enough positions. Such a factor, considered in all the splits in the BJMM is \(\left(\frac{\binom{(k+\ell/2)^{2}}{p_{3}}^{2}}{\binom{k+\ell}{p_{2}}}\right)^{4}\). The cost of an iteration of the loop at Lines 1-27 of the BJMM is as follows_

\[4\left(k+\ell+2(\tfrac{\frac{k+\ell}{p_{3}}}{p_{3}})+\ell_{2}+( \tfrac{\frac{k+\ell}{p_{3}}}{p_{3}})^{2}(2p_{3}\ell_{2})\right)+2\left(\left( \binom{\frac{P_{1}}{p_{1}/2})^{(k+\ell-P_{1})}{\epsilon_{2}}}{2^{\ell_{2}}}( \tfrac{\frac{k+\ell}{p_{3}}}{p_{3}})^{2}\right)^{2}(2p_{2}\ell_{1})\right)\] \[+\left(\tfrac{\binom{(\frac{P}{p_{2}/2})^{(k+\ell-P_{1})}}{ \epsilon_{1}}}{2^{\ell_{1}}}\left(\tfrac{\binom{P_{1}}{p_{1}/2})^{(k+\ell-P_{ 1})}}{2^{\ell_{2}}}(\tfrac{\frac{k+\ell}{p_{3}}}{p_{3}})^{2}\right)^{2}(2p_{1} \ell)+\frac{\left(\frac{(\frac{P}{p_{2}/2})^{(k+\ell-P_{1})}}{\epsilon_{1}}}{2 ^{\ell_{1}}}\left(\tfrac{\binom{P_{1}}{p_{1}/2})^{(k+\ell-P_{1})}}{2^{\ell_{2} }}(\tfrac{\frac{k+\ell}{p_{3}}}{p_{3}})^{2}\right)^{2}}{2^{\ell}}(p(r-\ell)).\]

_The first line constitutes the cost of the loop at Lines 4-16, the second line is the cost of the loop at Lines 17-23, the third line is the cost of the loop at Lines 24-27 save for the portion related to the branch at Line 25 being taken. The last line is the cost of computing the body of the taken branch, multiplied by the probability of such a branch being taken._

The BJMM variant of the ISD shares with the Stern, Finiasz and Sendrier, and May-Meurer-Thomae ISDs the fact that the exponential memory requirements should be taken into account by a logarithmic access cost, instead of a constant one.