{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T12:13:34Z","timestamp":1781180014591,"version":"3.54.1"},"reference-count":44,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T00:00:00Z","timestamp":1569888000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Decoding of random linear block codes has been long exploited as a computationally hard problem on which it is possible to build secure asymmetric cryptosystems. In particular, both correcting an error-affected codeword, and deriving the error vector corresponding to a given syndrome were proven to be equally difficult tasks. Since the pioneering work of Eugene Prange in the early 1960s, a significant research effort has been put into finding more efficient methods to solve the random code decoding problem through a family of algorithms known as information set decoding. The obtained improvements effectively reduce the overall complexity, which was shown to decrease asymptotically at each optimization, while remaining substantially exponential in the number of errors to be either found or corrected. In this work, we provide a comprehensive survey of the information set decoding techniques, providing finite regime temporal and spatial complexities for them. We exploit these formulas to assess the effectiveness of the asymptotic speedups obtained by the improved information set decoding techniques when working with code parameters relevant for cryptographic purposes. We also delineate computational complexities taking into account the achievable speedup via quantum computers and similarly assess such speedups in the finite regime. To provide practical grounding to the choice of cryptographically relevant parameters, we employ as our validation suite the ones chosen by cryptosystems admitted to the second round of the ongoing standardization initiative promoted by the US National Institute of Standards and Technology.<\/jats:p>","DOI":"10.3390\/a12100209","type":"journal-article","created":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T11:11:16Z","timestamp":1569928276000},"page":"209","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":36,"title":["A Finite Regime Analysis of Information Set Decoding Algorithms"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8754-5526","authenticated-orcid":false,"given":"Marco","family":"Baldi","sequence":"first","affiliation":[{"name":"Department of Information Engineering (DII), Universit\u00e0 Politecnica delle Marche, 60131 Ancona, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0840-6358","authenticated-orcid":false,"given":"Alessandro","family":"Barenghi","sequence":"additional","affiliation":[{"name":"Department of Electronics, Information and Bioengineering (DEIB), Politecnico di Milano, 20133 Milano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6994-1448","authenticated-orcid":false,"given":"Franco","family":"Chiaraluce","sequence":"additional","affiliation":[{"name":"Department of Information Engineering (DII), Universit\u00e0 Politecnica delle Marche, 60131 Ancona, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3812-5429","authenticated-orcid":false,"given":"Gerardo","family":"Pelosi","sequence":"additional","affiliation":[{"name":"Department of Electronics, Information and Bioengineering (DEIB), Politecnico di Milano, 20133 Milano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0631-3668","authenticated-orcid":false,"given":"Paolo","family":"Santini","sequence":"additional","affiliation":[{"name":"Department of Information Engineering (DII), Universit\u00e0 Politecnica delle Marche, 60131 Ancona, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,10,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","article-title":"On the inherent intractability of certain coding problems","volume":"24","author":"Berlekamp","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","first-page":"24","article-title":"A new class of linear correcting codes","volume":"6","author":"Goppa","year":"1970","journal-title":"Probl. Pered. Inf."},{"key":"ref_3","first-page":"159","article-title":"Knapsack-type cryptosystems and algebraic coding theory","volume":"15","author":"Niederreiter","year":"1986","journal-title":"Probl. Contr. Inf. Theory"},{"key":"ref_4","first-page":"439","article-title":"On insecurity of cryptosystems based on generalized Reed-Solomon codes","volume":"2","author":"Shestakov","year":"1978","journal-title":"Discret. Math. Appl."},{"key":"ref_5","unstructured":"Gaborit, P. (2005, January 14\u201318). Shorter Keys for Code Based Cryptography. Proceedings of the International Workshop on Coding and Cryptography 2015, Bergen, Norway."},{"key":"ref_6","unstructured":"Monico, C., Rosenthal, J., and Shokrollahi, A. (2000, January 25\u201330). Using Low Density Parity Check Codes in the McEliece Cryptosystem. Proceedings of the IEEE International Symposium on Information Theory (ISIT 2000), Sorrento, Italy."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1007\/978-3-642-05445-7_24","article-title":"Compact McEliece keys from Goppa codes","volume":"Volume 5867","author":"Misoczki","year":"2009","journal-title":"Selected Areas in Cryptography"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/978-3-540-85855-3_17","article-title":"A new analysis of the McEliece cryptosystem based on QC-LDPC codes","volume":"Volume 5229","author":"Baldi","year":"2008","journal-title":"Security and Cryptography for Networks"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Misoczki, R., Tillich, J.P., Sendrier, N., and Barreto, P.S.L.M. (2013, January 7\u201312). MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes. Proceedings of the IEEE International Symposium on Information Theory (ISIT 2013), Istanbul, Turkey.","DOI":"10.1109\/ISIT.2013.6620590"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1109\/TIT.1962.1057777","article-title":"The use of information sets in decoding cyclic codes","volume":"8","author":"Prange","year":"1962","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Lee, P.J., and Brickell, E.F. (1988, January 25\u201327). An Observation on the Security of McEliece\u2019s Public-Key Cryptosystem. Proceedings of the Advances in Cryptology\u2014EUROCRYPT \u201988, Workshop on the Theory and Application of of Cryptographic Techniques, Davos, Switzerland.","DOI":"10.1007\/3-540-45961-8_25"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1354","DOI":"10.1109\/18.21270","article-title":"A probabilistic algorithm for computing minimum weights of large error-correcting codes","volume":"34","author":"Leon","year":"1988","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","unstructured":"Stern, J. (1988, January 2\u20134). A Method for Finding Codewords of Small Weight. Proceedings of the Coding Theory and Applications, 3rd International Colloquium, Toulon, France."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Finiasz, M., and Sendrier, N. (2009, January 6\u201310). Security Bounds for the Design of Code-Based Cryptosystems. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan.","DOI":"10.1007\/978-3-642-10366-7_6"},{"key":"ref_15","unstructured":"May, A., Meurer, A., and Thomae, E. (2011, January 4\u20138). Decoding random linear codes in \u00d5(20.054n). Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2011\u201417th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, Korea."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Becker, A., Joux, A., May, A., and Meurer, A. (2012, January 15\u201319). Decoding Random Binary Linear Codes in 2n\/20: How 1 + 1 = 0 Improves Information Set Decoding. Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2012\u201431st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK.","DOI":"10.1007\/978-3-642-29011-4_31"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.1109\/18.57202","article-title":"The complexity of information set decoding","volume":"36","author":"Coffey","year":"1990","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","first-page":"103","article-title":"Decoding complexity bound for linear block codes","volume":"25","author":"Kruk","year":"1989","journal-title":"Probl. Peredachi Inf."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1392","DOI":"10.1109\/18.771141","article-title":"On the complexity of minimum distance decoding of long linear codes","volume":"45","author":"Barg","year":"1999","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","first-page":"5","article-title":"Problems of complexity in the theory of correcting codes","volume":"13","author":"Bassalygo","year":"1977","journal-title":"Probl. Peredachi Inf."},{"key":"ref_21","unstructured":"Barg, A. (2019, September 27). Complexity Issues in Coding Theory. Available online: https:\/\/eccc.weizmann.ac.il\/eccc-reports\/1997\/TR97-046\/Paper.pdf."},{"key":"ref_22","unstructured":"Pless, V.S. (1998). Handbook of Coding Theory, Elsevier Science Inc."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Kabatiansky, G., Krouk, E., and Semenov, S. (2005). Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept, Wiley Inc.","DOI":"10.1002\/0470867574"},{"key":"ref_24","unstructured":"USA National Institute of Standards and Technology (2016). Post-Quantum Crypto Project."},{"key":"ref_25","first-page":"162","article-title":"A non asymptotic analysis of information set decoding","volume":"2013","author":"Hamdaoui","year":"2013","journal-title":"IACR Cryptol. EPrint Arch."},{"key":"ref_26","unstructured":"Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., and Santini, P. (2019, September 27). LEDAtools. Available online: https:\/\/github.com\/LEDAcrypt\/LEDAtools."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Arora, S., and Barak, B. (2009). Computational Complexity\u2014A Modern Approach, Cambridge University Press.","DOI":"10.1017\/CBO9780511804090"},{"key":"ref_28","unstructured":"Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., Rosenthal, J., Santini, P., and Schipani, D. (2018). Design and implementation of a digital signature scheme based on low-density generator matrix codes. arXiv."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., and Santini, P. (2018). LEDAkem: A post-quantum key encapsulation mechanism based on QC-LDPC codes. arXiv.","DOI":"10.1007\/978-3-319-79063-3_1"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., and Santini, P. (2018, January 9\u201311). LEDAkem: A Post-Quantum Key Encapsulation Mechanism Based on QC-LDPC Codes. Proceedings of the Post-Quantum Cryptography\u20149th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA.","DOI":"10.1007\/978-3-319-79063-3_1"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., and Santini, P. (2019, January 18\u201319). LEDAcrypt: QC-LDPC Code-Based Cryptosystems with Bounded Decryption Failure Rate. Proceedings of the Code-Based Cryptography, 7th International Workshop, CBC 2019, Darmstadt, Germany.","DOI":"10.1007\/978-3-030-25922-8_2"},{"key":"ref_32","unstructured":"McEliece, R.J. (2019, September 27). A Public-Key Cryptosystem Based on Algebraic Coding Theory, Available online: https:\/\/ntrs.nasa.gov\/archive\/nasa\/casi.ntrs.nasa.gov\/19780016269.pdf."},{"key":"ref_33","unstructured":"Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., and Santini, P. (2019, September 27). LEDAcrypt Website. Available online: https:\/\/www.ledacrypt.org\/."},{"key":"ref_34","unstructured":"Aragon, N., Barreto, P.S.L.M., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Gueron, S., Guneysu, T., and Aguilar Melchor, C. (2019, September 27). BIKE: Bit Flipping Key Encapsulation, 2017. NIST Post-Quantum Cryptography Project: First Round Candidate Algorithms. Available online: https:\/\/bikesuite.org\/."},{"key":"ref_35","unstructured":"MacKay, D.J.C. (2003). Information Theory, Inference and Learning Algorithms, Cambridge University Press. [1st ed.]."},{"key":"ref_36","first-page":"377","article-title":"Improved generalized birthday attack","volume":"2011","author":"Kirchner","year":"2011","journal-title":"IACR Cryptol. EPrint Arch."},{"key":"ref_37","unstructured":"Niebuhr, R., Cayrel, P.L., and Buchmann, J. (2011, January 11\u201315). Improving the Efficiency of Generalized Birthday Attacks against Certain Structured Cryptosystems. Proceedings of the Workshop on Coding And Cryptography (WCC 2011), Paris, France."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Sendrier, N. (December, January 29). Decoding One Out of Many. Proceedings of the Post-Quantum Cryptography\u20144th International Workshop, PQCrypto 2011, Taipei, Taiwan.","DOI":"10.1007\/978-3-642-25405-5_4"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Grover, L.K. (1996, January 22\u201324). A Fast Quantum Mechanical Algorithm for Database Search. Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadephia, PA, USA.","DOI":"10.1145\/237814.237866"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Sendrier, N. (2010). Grover vs. McEliece. Post-Quantum Cryptography, Springer.","DOI":"10.1007\/978-3-642-12929-2"},{"key":"ref_41","unstructured":"De Vries, S. (2016). Achieving 128-Bit Security Against Quantum Attacks in OpenVPN. [Master\u2019s Thesis, University of Twente]."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Kachigar, G., and Tillich, J. (2017, January 26\u201328). Quantum Information Set Decoding Algorithms. Proceedings of the Post-Quantum Cryptography\u20148th International Workshop, PQCrypto 2017, Utrecht, The Netherlands.","DOI":"10.1007\/978-3-319-59879-6_5"},{"key":"ref_43","unstructured":"Bernstein, D.J., Chou, T., Lange, T., Maurich, I.V., Misoczki, R., Niederhagen, R., Persichetti, E., Peters, C., Schwabe, P., and Sendrier, N. (2019, September 27). Classic McEliece: Conservative Code-Based Cryptography, 2019. NIST Post-Quantum Cryptography Project: Second Round Candidate Algorithms, Available online: https:\/\/csrc.nist.gov\/Projects\/Post-Quantum-Cryptography\/Round-2-Submissions."},{"key":"ref_44","unstructured":"Albrecht, M., Cid, C., Paterson, K.G., Tjhai, C.J., and Tomlinson, M. (2019, September 27). NTS-KEM, 2019. NIST Post-Quantum Cryptography Project: Second Round Candidate Algorithms, Available online: https:\/\/csrc.nist.gov\/Projects\/Post-Quantum-Cryptography\/Round-2-Submissions."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/209\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:26:45Z","timestamp":1760189205000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,1]]},"references-count":44,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,10]]}},"alternative-id":["a12100209"],"URL":"https:\/\/doi.org\/10.3390\/a12100209","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,1]]}}}