{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T10:55:27Z","timestamp":1776941727161,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642290107","type":"print"},{"value":"9783642290114","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29011-4_31","type":"book-chapter","created":{"date-parts":[[2012,4,5]],"date-time":"2012-04-05T07:05:53Z","timestamp":1333609553000},"page":"520-536","source":"Crossref","is-referenced-by-count":253,"title":["Decoding Random Binary Linear Codes in 2 n\/20: How 1\u2009+\u20091\u2009=\u20090 Improves Information Set Decoding"],"prefix":"10.1007","author":[{"given":"Anja","family":"Becker","sequence":"first","affiliation":[]},{"given":"Antoine","family":"Joux","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"May","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Meurer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on Average Case vs Approximation Complexity. In: 44th Symposium on Foundations of Computer Science (FOCS), pp. 298\u2013307 (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"31_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-20465-4_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"A. Becker","year":"2011","unstructured":"Becker, A., Coron, J.-S., Joux, A.: Improved Generic Algorithms for Hard Knapsacks. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol.\u00a06632, pp. 364\u2013385. Springer, Heidelberg (2011)"},{"key":"31_CR3","unstructured":"Becker, A., Joux, A., May, A., Meurer, A.: Decoding Random Binary Linear Codes in 2 n\/20: How 1\u2009+\u20091\u2009=\u20090 Improves Information Set Decoding. Full Version, http:\/\/eprint.iacr.org"},{"key":"31_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-88403-3_3","volume-title":"Post-Quantum Cryptography","author":"D.J. Bernstein","year":"2008","unstructured":"Bernstein, D.J., Lange, T., Peters, C.: Attacking and Defending the McEliece Cryptosystem. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol.\u00a05299, pp. 31\u201346. Springer, Heidelberg (2008)"},{"key":"31_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1007\/978-3-642-22792-9_42","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"D.J. Bernstein","year":"2011","unstructured":"Bernstein, D.J., Lange, T., Peters, C.: Smaller Decoding Exponents: Ball-Collision Decoding. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 743\u2013760. Springer, Heidelberg (2011)"},{"key":"31_CR6","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"R.J.M. Elwyn","year":"1978","unstructured":"Elwyn, R.J.M., Berlekamp, R., van Tilborg, H.C.: On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory\u00a024, 384\u2013386 (1978)","journal-title":"IEEE Transactions on Information Theory"},{"key":"31_CR7","first-page":"50","volume":"23","author":"V.M. Blinovskii","year":"1987","unstructured":"Blinovskii, V.M.: Lower asymptotic bound on the number of linear code words in a sphere of given radius in ${\\mathbb{F}_q^n}$ . Probl. Peredach. Inform.\u00a023, 50\u201353 (1987)","journal-title":"Probl. Peredach. Inform."},{"issue":"1","key":"31_CR8","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1109\/18.651067","volume":"44","author":"A. Canteaut","year":"1998","unstructured":"Canteaut, A., Chabaud, F.: A new algorithm for finding minimum-weight words in a linear code: Application to mceliece\u2019s cryptosystem and to narrow-sense bch codes of length 511. IEEE Transactions on Information Theory\u00a044(1), 367\u2013378 (1998)","journal-title":"IEEE Transactions on Information Theory"},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1109\/18.57202","volume":"36","author":"J.T. Coffey","year":"1990","unstructured":"Coffey, J.T., Goodman, R.M.: The complexity of information set decoding. IEEE Transactions on Information Theory\u00a036, 1031\u20131037 (1990)","journal-title":"IEEE Transactions on Information Theory"},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"Coffey, J.T., Goodman, R.M.: Any code of which we cannot think is good. IEEE Transactions on Information Theory\u00a036 (1990)","DOI":"10.1109\/18.59944"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: A Distinguisher for High Rate McEliece Cryptosystems. In: YACC 2010, full version available as eprint Report 2010\/331 (2010)","DOI":"10.1109\/ITW.2011.6089437"},{"key":"31_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-642-10366-7_6","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"M. Finiasz","year":"2009","unstructured":"Finiasz, M., Sendrier, N.: Security Bounds for the Design of Code-Based Cryptosystems. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.\u00a05912, pp. 88\u2013105. Springer, Heidelberg (2009)"},{"key":"31_CR13","unstructured":"Goblick Jr., T.J.: Coding for a discrete information source with a distortion measure. Ph.D. dissertation, Dept. of Elect. Eng. M.I.T., Cambridge, MA (1962)"},{"key":"31_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-45682-1_4","volume-title":"Advances in Cryptology - ASIACRYPT 2001","author":"N.J. Hopper","year":"2001","unstructured":"Hopper, N.J., Blum, M.: Secure Human Identification Protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol.\u00a02248, pp. 52\u201366. Springer, Heidelberg (2001)"},{"key":"31_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-13190-5_12","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"N. Howgrave-Graham","year":"2010","unstructured":"Howgrave-Graham, N., Joux, A.: New Generic Algorithms for Hard Knapsacks. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 235\u2013256. Springer, Heidelberg (2010)"},{"key":"31_CR16","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/1008908.1008918","volume":"15","author":"J.P. Jordan","year":"1983","unstructured":"Jordan, J.P.: A variant of a public key cryptosystem based on goppa codes. SIGACT News\u00a015, 61\u201366 (1983)","journal-title":"SIGACT News"},{"key":"31_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/978-3-642-20465-4_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"E. Kiltz","year":"2011","unstructured":"Kiltz, E., Pietrzak, K., Cash, D., Jain, A., Venturi, D.: Efficient Authentication from Hard Learning Problems. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol.\u00a06632, pp. 7\u201326. Springer, Heidelberg (2011)"},{"key":"31_CR18","unstructured":"Knuth, D.: Art of Computer Programming: Sorting and Searching, 2nd edn., vol.\u00a03. Addison-Wesley Professional (1998)"},{"key":"31_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/3-540-45961-8_25","volume-title":"Advances in Cryptology - EUROCRYPT \u201988","author":"P.J. Lee","year":"1988","unstructured":"Lee, P.J., Brickell, E.F.: An Observation on the Security of McEliece\u2019s Public-Key Cryptosystem. In: G\u00fcnther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol.\u00a0330, pp. 275\u2013280. Springer, Heidelberg (1988)"},{"issue":"5","key":"31_CR20","doi-asserted-by":"publisher","first-page":"1354","DOI":"10.1109\/18.21270","volume":"34","author":"J.S. Leon","year":"1988","unstructured":"Leon, J.S.: A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Transactions on Information Theory\u00a034(5), 1354\u20131359 (1988)","journal-title":"IEEE Transactions on Information Theory"},{"key":"31_CR21","unstructured":"Levitin, L.B.: Covering radius of almost all linear codes satisfies the Goblick bound. In: IEEE Internat. Symp. on Information Theory, Kobe, Japan (1988)"},{"key":"31_CR22","unstructured":"McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. In: Jet Propulsion Laboratory DSN Progress Report 42\u201344, pp. 114\u2013116 (1978)"},{"key":"31_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-25385-0_6","volume-title":"ASIACRYPT 2011","author":"A. May","year":"2011","unstructured":"May, A., Meurer, A., Thomae, E.: Decoding Random Linear Codes in $\\tilde{\\mathcal{O}}(2^{0.054n})$ . In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol.\u00a07073, pp. 107\u2013124. Springer, Heidelberg (2011)"},{"key":"31_CR24","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q., Shparlinski, I.E., Stern, J.: Distribution of modular sums and the security of the server aided exponentiation. In: Progress in Computer Science and Applied Logic. Final Proceedings of Cryptography and Computational Number Theory Workshop, Singapore 1999, vol. 20, pp. 331\u2013224 (2001)","DOI":"10.1007\/978-3-0348-8295-8_24"},{"issue":"5","key":"31_CR25","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1109\/TIT.1962.1057777","volume":"8","author":"E. Prange","year":"1962","unstructured":"Prange, E.: The Use of Information Sets in Decoding Cyclic Codes. IRE Transaction on Information Theory\u00a08(5), 5\u20139 (1962)","journal-title":"IRE Transaction on Information Theory"},{"key":"31_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-642-12929-2_7","volume-title":"Post-Quantum Cryptography","author":"C. Peters","year":"2010","unstructured":"Peters, C.: Information-Set Decoding for Linear Codes over ${\\mathbb{F}_q}$ . In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol.\u00a06061, pp. 81\u201394. Springer, Heidelberg (2010)"},{"key":"31_CR27","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 84\u201393 (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"31_CR28","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1109\/18.850662","volume":"46","author":"N. Sendrier","year":"2000","unstructured":"Sendrier, N.: Finding the permutation between equivalent linear codes: The support splitting algorithm. IEEE Transactions on Information Theory\u00a046, 1193\u20131203 (2000)","journal-title":"IEEE Transactions on Information Theory"},{"key":"31_CR29","doi-asserted-by":"crossref","unstructured":"Sendrier, N.: On the security of the McEliece public-key cryptosystem. In: Blaum, M., Farrell, P., van Tilborg, H. (eds.) Information, Coding and Mathematics, pp. 141\u2013163. Kluwer (2002); Proceedings of Workshop honoring Prof. Bob McEliece on his 60th birthday","DOI":"10.1007\/978-1-4757-3585-7_10"},{"key":"31_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/BFb0019850","volume-title":"Coding Theory and Applications","author":"J. Stern","year":"1989","unstructured":"Stern, J.: A Method for Finding Codewords of Small Weight. In: Wolfmann, J., Cohen, G. (eds.) Coding Theory 1988. LNCS, vol.\u00a0388, pp. 106\u2013113. Springer, Heidelberg (1989)"},{"key":"31_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-45708-9_19","volume-title":"Advances in Cryptology - CRYPTO 2002","author":"D. Wagner","year":"2002","unstructured":"Wagner, D.: A Generalized Birthday Problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol.\u00a02442, pp. 288\u2013303. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29011-4_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T13:52:58Z","timestamp":1742910778000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29011-4_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642290107","9783642290114"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29011-4_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}