# A Finite Regime Analysis of Information Set Decoding Algorithms
## 2 Background on Computationally Intractable Coding Theory Problems  
In this section, we introduce the notation and background on error correcting codes, and state which hard problems we focus on, for which best solvers are ISD algorithms. In the following, we consider the case of binary linear block codes, denoting as \(\mathcal{C}(n,k,d)\) a code of length \(n\), dimension \(k\) and minimum distance \(d\). This code is thus a subspace of \(\{0,1\}^{n}\) containing \(2^{k}\) distinct vectors, and can be represented by a \(k\times n\) binary matrix \(G\) known as the code generator matrix. It is commonplace to indicate with \(r=n-k\) the amount of redundant bits in an element of the code, i.e., a codeword. The minimum distance of a linear block code corresponds to the minimum weight of its codewords, apart from the null one (which, clearly, has null weight). An alternative representation is the one provided by the so-called parity check matrix \(H\), which is obtained through the algebraic constraint \(HG^{T}=0_{r\times k}\). The parity check is thus an \(r\times n\) binary matrix for which it is easy to show that the product of a codeword \(c\) by \(H\) is a null \(r\)-bit-long vector. The quantity obtained multiplying a generic \(n\)-bit vector \(\tilde{c}\) by \(H\) is called the syndrome \(s=H\tilde{c}^{T}\) of \(\tilde{c}\) through \(H\). Note that, if the binary vector \(\tilde{c}\) is not a codeword, the syndrome of \(\tilde{c}\) through \(H\) is not null; in other words, we can write \(\tilde{c}=c+e\), with \(c\) being a codeword, and thus have \(s=He^{T}\). Decoding of \(\tilde{c}\) through \(\mathcal{C}(n,k,d)\) consists in finding the codeword \(c\) whose distance from \(\tilde{c}\) is minimum. The procedure of finding a length-\(n\) binary vector \(e\), with Hamming weight smaller than or equal to some integer \(t\), given a non-null syndrome \(s\) and a parity matrix \(H\) is known as syndrome decoding. The name stems from the fact that decoding a given \(\tilde{c}\) becomes possible by computing the syndrome \(s\) of \(\tilde{c}\), solving the syndrome decoding, and adding the obtained vector \(e\) to \(\tilde{c}\), and corresponds to finding the codeword which is at minimum distance from \(\tilde{c}\). We can now recall the two decisional problems in coding theory which were proven to be NP-Complete by [PERSON] et al. in [1], and from which the main building blocks of the cryptographic trapdoors of code-based cryptosystems are derived. **Statement 1** (Coset weights problem). : _Given a random, \(r\times n\) binary matrix \(H\), an \(r\) bit vector \(s\) and a positive integer \(t\), determine if an \(n\) bit vector \(e\) with \(wt(e)\leq t\), where \(wt(\cdot)\) is the Hamming weight function, such that \(He^{T}=s\) exists._  
The Coset weights problem is also known as the Decisional Syndrome Decoding Problem (DSDP). **Statement 2** (Subspace weights problem). : _Given a random, \(r\times n\) binary matrix \(H\), and a positive integer \(w\), determine if an \(n\) bit vector \(c\) with \(wt(c)=t\), where \(wt(\cdot)\) is the Hamming weight function, such that \(Hc^{T}=0_{r\times 1}\) exists._  
The Subspace weights problem is also known as the Decisional Codeword Finding Problem (DCFP). The typical hard problems which are employed to build code-based cryptographic trapdoors are the search variants of the aforementioned two problems. Specifically, the Syndrome Decoding Problem (SDP) asks to _find_ an error vector of weight \(\leq\)\(t\), while the Codeword Finding Problem (CFP) asks to _find_ a codeword with a given weight \(w\). A well known result in computational complexity theory (e.g., [27] Chap. 2.5) states that any decision problem belonging to the NP-Complete class has a search-to-decision reduction. In other words, it is possible to solve an instance of the search problemwith a polynomial amount of calls to an oracle for the corresponding decision problem.