# A Finite Regime Analysis of Information Set Decoding Algorithms
## 2 Background on Computationally Intractable Coding Theory Problems
### Strategies to Perform MRA  
As described in the previous section, security of code-based cryptosystems relies on the hardness of solving Syndrome Decoding Problem (SDP) or Codeword Finding Problem (CFP) instances. In this section, we analyze the case of Syndrome Decoding Problem (SDP) and show that the optimal strategy to perform Message Recovery Attack (MRA) depends on the code parameters. The optimal strategy for solving Syndrome Decoding Problem (SDP) depends on the relation between the actual parameters of the instance under analysis. In particular, in the cases where \(t\) is above the Gilbert-Varshamov (GV) distance [35], Generalized Birthday Algorithm (GBA) is the best currently known algorithm for solving Syndrome Decoding Problem (SDP) [36; 37]. However, for the cases we consider in this paper, practical values of \(t\) are significantly smaller than the GV distance; in such cases, the best known methods to solve Syndrome Decoding Problem (SDP) go by the name of Information Set Decoding (ISD) algorithms. Such algorithms are aimed at lessening the computational effort required in the guesswork of an exhaustive search for the unknown error vector \(e\) of weight \(t\), given a syndrome and a parity check matrix. We point out that it is also possible to adapt all Information Set Decoding (ISD) algorithms, save for the first one proposed by [PERSON] [10], to solve the Codeword Finding Problem (CFP), as a consequence of the structural similarity of the two problems. All Information Set Decoding (ISD) algorithms share a common structure where an attempt at retrieving the error vector corresponding to a given syndrome is repeated, for a number of times whose average value depends on the success probability of the single attempt itself. The complexity of all Information Set Decoding (ISD) variants can be expressed as the product between the complexity of each attempt, which we denote as \(C_{\text{iter}}\), and the average number of required attempts. In particular, such a value can be obtained as the reciprocal of the success probability of each attempt, which we denote as \(\Pr_{\text{succ}}\); thus, when considering a code with length \(n\), redundancy \(r=n-k\) and Hamming weight of the sought error bounded to \(t\), we generically denote the time complexity of obtaining one solution of Syndrome Decoding Problem (SDP) employing the Information Set Decoding (ISD) variant at hand, i.e.,  
\[C_{\text{ISD}}(n,r,t)=\frac{C_{\text{iter}}}{\Pr_{\text{succ}}}. \tag{1}\]  
As we show in the following, the work factor of a Message Recovery Attack (MRA) performed through Information Set Decoding (ISD) may actually depend on the system parameters; to this end, we first exploit the following well-known result. Let \(\mathcal{C}(n,k,d)\) be a linear binary code with length \(n\), dimension \(k\) and minimum distance \(d\), and let \(H\) be a parity-check matrix for \(\mathcal{C}(n,k,d)\). Let \(s\) be a length-\(r\) binary vector and \(t\) be an integer \(\leq\)\(n\); then, if \(t<\left\lceil\frac{d}{2}\right\rceil\), there is at maximum one vector \(e\) of weight \(t\) such that \(s=He^{T}\). Thus, when \(H_{pub}\) is the parity-check matrix of a code with minimum distance \(d>2t\), then solving Syndrome Decoding Problem (SDP) guarantees that the found error vector corresponds to the one that was used to encrypt the message. In this case, the attack work factor corresponds to \(C_{\text{ISD}}(n,r,t)\). However, when \(d\leq 2t\), the time complexity of a Message Recovery Attack (MRA) needs to be derived through a different approach. Indeed, in such a case, the adversary has no guarantee that the output of Information Set Decoding (ISD) corresponds to the error vector that was actually used in the encryption phase. Thus, the work factor of a Message Recovery Attack (MRA) cannot be simply taken as the time complexity of the chosen Information Set Decoding (ISD) algorithm. Let \(s\) be the syndrome corresponding to the intercepted ciphertext and \(e\) be the searched error vector, i.e., \(s=H_{pub}e^{T}\).