# A Finite Regime Analysis of Information Set Decoding Algorithms
## 2 Background on Computationally Intractable Coding Theory Problems
### Applications to Cryptography  
The class of NP-Complete problems is of particular interest to design cryptosystems, as it is widely believed that problems contained in such a class cannot be solved in polynomial time by a quantum computer. Indeed, the best known approaches to solve both the Codeword Finding Problem (CFP) and the Syndrome Decoding Problem (SDP) have a computational complexity which is exponential in the weight of the codeword or error vector to be found. A notable example of code-based cryptosystem relying on the hardness of the Syndrome Decoding Problem (SDP) is the one proposed by [PERSON] in [PERSON] (1999). [PERSON] cryptosystem generates a public-private key-pair selecting as the private key an instance of a code from a family for which efficient decoding algorithms are available. The code is then represented by its parity check matrix \(H_{priv}\), which is multiplied by a rank-\(r\) random square binary matrix \(S\) obtaining the public key of the cryptosystem \(H_{pub}=SH_{priv}\). The assumption made by [PERSON] is that the multiplication by the random, full rank matrix \(S\) makes \(H_{pub}\) essentially indistinguishable from a random parity matrix. While the original choice to employ a Reed-Solomon code as private code was found to falsify this assumption and lead to a practical attack, other code families have proven to be good candidates (e.g., Goppa codes, Low/Medium Density Parity Check codes ([PERSON], 1999; [PERSON], 2000; [PERSON], 2001; [PERSON], 2002)). A message is encrypted in the Niederreiter cryptosystem encoding it as a fixed weight error vector \(e\) and computing its syndrome through \(H_{pub}\), \(s=H_{pub}e^{T}\), which acts as the ciphertext. The owner of the private key \((S,H_{priv})\) is able to decipher the ciphertext through first obtaining \(s^{\prime}=S^{-1}s\) and subsequently performing the syndrome decoding of \(s^{\prime}\) employing \(H_{priv}\). It is easy to note that, under the assumption that \(H_{pub}\) is indistinguishable from a random parity check matrix, an attacker willing to perform a Message Recovery Attack (MRA) must solve an instance of the Syndrome Decoding Problem (SDP). We note that, as proven by [PERSON] (1999), the Syndrome Decoding Problem (SDP) is computationally equivalent to the problem of correcting a bounded amount of errors affecting a codeword, when given a random generator matrix of the code, \(G\). Such a problem goes by the name of Decoding Problem, and is the mainstay of the original cryptosystem proposal by [PERSON] (2000). In such a scheme, the ciphertext thus corresponds to the sum between a codeword of the public code, obtained as \(mG\), with \(m\) being a length-\(k\) vector, and a vector \(e\) of weight \(t\). The message can either be encoded into \(e\) or into \(m\); in the latter case, Message Recovery Attack (MRA) is performed by searching for the error vector \(e\) and, subsequently, by adding it to the intercepted ciphertext. We point out that this search can automatically turned into the formulation of Syndrome Decoding Problem (SDP), by first computing a valid \(H_{pub}\) from \(G\) and then by trying to solve Syndrome Decoding Problem (SDP) on the syndrome of the intercepted ciphertext through \(H_{pub}\). One of the most prominent cases where Codeword Finding Problem (CFP) appears in code-based cryptosystems is represented by a Key Recovery Attack (KRA) against Niederreiter cryptosystems where the private parity check matrix \(H_{priv}\) contains rows with a known low weight \(w\). Indeed, in such a case, considering \(H_{pub}\) as the generator matrix of the dual code, solving the Codeword Finding Problem (CFP) for such a code reveals the low weight rows of \(H_{priv}\). We note that such a Key Recovery Attack (KRA) is in the same computational complexity class as Syndrome Decoding Problem (SDP), assuming that the obfuscation of \(H_{pub}\) makes it indistinguishable from a random one.