# A Finite Regime Analysis of Information Set Decoding Algorithms
## 1 Introduction  
Asymmetric cryptosystems are traditionally built on a mathematical function which is hard to compute unless the knowledge of a special parameter is available. Typically, such a function is known as a mathematical trapdoor, and the parameter acts as the private key of the asymmetric cryptosystem. Decoding a random linear block code was first proven to be equivalent to solve an instance of the three dimensional matching by [PERSON] et al. in 1978 [1]. By contrast, efficient decoding algorithms for well structured codes have a long history of being available. Therefore, [PERSON] himself proposed to disguise an efficiently decodable code as a random code and employ the knowledge of the efficiently decodable representation as the private key of an asymmetric cryptosystem. In this way, a legitimate user of the cryptosystem would be able to employ an efficient decoder for the chosen hidden code, while an attacker would be forced to resort to decoding techniques for a generic linear code. Since the original proposal, a significant amount of variants of the [PERSON] cryptosystem were proposed swapping the original decodable code choice (Goppa codes [2]) with other efficientlydecodable codes with the intent of enhancing computational performances of reducing the key size. The first attempt in this direction was the Niederreiter cryptosystem [3] using generalized Reed-Solomon (GRS) codes. While the original proposal by [PERSON] was broken by [PERSON] and [PERSON] in [4], replacing the hidden code with a Goppa code in [PERSON]'s proposal yields a cryptosystem which is currently unbroken. More recently, other families of structured codes have been considered in this framework, such as Quasi Cyclic (QC) codes [5], Low Density Parity Check (LDPC) codes [6], Quasi Dyadic (QD) codes [7], Quasi Cyclic Low Density Parity Check (QC-LDPC) codes [8] and Quasi Cyclic Moderate Density Parity Check (QC-MDPC) codes [9]. The significant push in the development of code-based cryptosystems was also accompanied by a comparably sized research effort in their cryptanalysis. In particular, the best attack technique that does not rely on the underlying hidden code structure, and thus is applicable to all the variants, is known as Information Set Decoding (ISD). In a nutshell, ISD attempts at finding enough error-free locations in a codeword to be able to decode it regardless of the errors which affect the codeword itself. Such a technique was first proposed by [PERSON] [10] as a more efficient alternative to decode a general linear block code, with respect to a straightforward guess on the error affected locations. Since then, a significant amount of improvements to [PERSON]'s original technique were proposed [11; 12; 13; 14; 15; 16], effectively providing significant polynomial speedups on the exponential-time decoding task. In addition to the former works, where the focus is to propose an operational description of a general decoding technique based on information set decoding, the works by the authors of [17; 18; 19] provide a more general view on general decoding techniques, including split syndrome decoding and supercode decoding, and report proven bounds on the complexities of the said approaches. Finally, we report the work of [PERSON] et al. [20] as the first tackling formally the complexity of decoding linear codes. For a more comprehensive survey of hard problems in coding theory, we refer the interested reader to [21; 22; 23]. The common praxis in the literature concerning ISD improvements is to evaluate the code parameters for the worst-case-scenario of the ISD, effectively binding together the code rate and number of corrected errors to the code length. Subsequently, the works analyze the asymptotic speedup as a function of the code length alone. While this approach is effective in showing an improvement in the running time of the ISD in principle, the practical relevance of the improvement when considering useful parameter sizes in cryptography may be less significant.