# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
To provide insights on the effectiveness of asymptotic estimates for the Information Set Decoding (ISD) complexities, we evaluate them on a set of parameters chosen by code-based cryptosystems submitted to the current NIST standardization effort for post quantum cryptography. Our results show that the May-Meurer-Thomae variant of the Information Set Decoding (ISD) may be preferable in the case an actual attack is implemented against the cryptosystems at hand. Moreover, we also report that the simple approximation provided in [34] for the asymptotic cost of an Information Set Decoding (ISD) appears to be overestimating the complexity of the attack in the finite regime, by a small but significant amount. In light of the obtained results, we deem a practical evaluation of the complexities of the described algorithms on reduced security instances of the cryptosystems at hand an interesting topic for further investigation. Conceptualization, M.B., A.B., F.C., G.P. and P.S. Writing - original draft, M.B., A.B., F.C., G.P. and P.S. This research received no external funding. The authors declare no conflict of interest. ## References

* (1) [PERSON]; [PERSON]; [PERSON]. On the inherent intractability of certain coding problems. _IEEE Trans. Inf. Theory_**1978**, _24_, 384-386. [CrossRef]
* (2) [PERSON] A new class of linear correcting codes. _Probl. Pered. Inf._**1970**, \(6\), 24-30. * (3) [PERSON] Knapsack-type cryptosystems and algebraic coding theory. _Probl. Contr. Inf. Theory_**1986**, _15_, 159-166. * (4) [PERSON]; [PERSON] On insecurity of cryptosystems based on generalized Reed-Solomon codes. _Discret. Math. Appl._**1978**, \(2\), 439-444. [CrossRef]
* (5) [PERSON] Shorter Keys for Code Based Cryptography. In Proceedings of the International Workshop on Coding and Cryptography 2015, Bergen, Norway, 14-18 March 2005; pp. 81-90. * (6) [PERSON]; [PERSON]; [PERSON] Using Low Density Parity Check Codes in the McEliece Cryptosystem. In Proceedings of the IEEE International Symposium on Information Theory (ISIT 2000), Sorrento, Italy, 25-30 June 2000; p. 215. * (7) [PERSON]; [PERSON]. Compact McEliece keys from Goppa codes. In _Selected Areas in Cryptography_, Springer: Berlin/Heidelberg, Germany, 2009; Volume 5867, pp. 376-392. * (8) [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON] A new analysis of the McEliece cryptosystem based on QC-LDPC codes. In _Security and Cryptography for Networks_; Springer: Berlin/Heidelberg, Germany, 2008; Volume 5229, pp. 246-262. * (9) [PERSON]; [PERSON]; [PERSON]; [PERSON]. MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes. In Proceedings of the IEEE International Symposium on Information Theory (ISIT 2013), Istanbul, Turkey, 7-12 July 2013; pp. 2069-2073. * (10) [PERSON] The use of information sets in decoding cyclic codes. _IRE Trans. Inf. Theory_**1962**, \(8\), 5-9. [CrossRef]
* (11) [PERSON]; [PERSON] An Observation on the Security of McEliece's Public-Key Cryptosystem. In Proceedings of the Advances in Cryptology--EUROCRYPT '88, Workshop on the Theory and Application of of Cryptographic Techniques, Davos, Switzerland, 25-27 May 1988; pp. 275-280. * (12) [PERSON] A probabilistic algorithm for computing minimum weights of large error-correcting codes. _IEEE Trans. Inf. Theory_**1988**, _34_, 1354-1359. [CrossRef]
* (13) [PERSON] A Method for Finding Codewords of Small Weight. In Proceedings of the Coding Theory and Applications, 3 rd International Colloquium, Toulon, France, 2-4 November 1988; pp. 106-113. * [PERSON] and [PERSON] (2009) [PERSON]; [PERSON] [PERSON] Security Bounds for the Design of Code-Based Cryptosystems. In Proceedings of the Advances in Cryptology--ASIACRYPT 2009, 15 th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, 6-10 December 2009; pp. 88-105. * [PERSON] et al. (2011) [PERSON]; [PERSON]; [PERSON] Decoding random linear codes in \(\tilde{O}(2^{0.054n})\).