{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T12:13:36Z","timestamp":1781180016295,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":77,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642227912","type":"print"},{"value":"9783642227929","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22792-9_42","type":"book-chapter","created":{"date-parts":[[2011,8,5]],"date-time":"2011-08-05T15:32:14Z","timestamp":1312558334000},"page":"743-760","source":"Crossref","is-referenced-by-count":129,"title":["Smaller Decoding Exponents: Ball-Collision Decoding"],"prefix":"10.1007","author":[{"given":"Daniel J.","family":"Bernstein","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tanja","family":"Lange","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christiane","family":"Peters","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"#cr-split#-42_CR1.1","doi-asserted-by":"crossref","unstructured":"Adams, C.M., Meijer, H.: Security-related comments regarding McEliece???s public-key cryptosystem. In: Crypto???87 [46], pp. 224???228 (1987);","DOI":"10.1007\/3-540-48184-2_20"},{"key":"#cr-split#-42_CR1.2","unstructured":"See also newer version [2]; Citations in this document:"},{"key":"42_CR2","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1109\/18.32140","volume":"35","author":"C.M. Adams","year":"1988","unstructured":"Adams, C.M., Meijer, H.: Security-related comments regarding McEliece\u2019s public-key cryptosystem. IEEE Transactions on Information Theory\u00a035, 454\u2013455 (1988); See also older version [1]; Citations in this document:","journal-title":"IEEE Transactions on Information Theory"},{"key":"#cr-split#-42_CR3.1","doi-asserted-by":"crossref","unstructured":"Al Jabri, A.: A statistical decoding algorithm for general linear block codes. In: IMA 2001 [31], pp. 1???8 (2001);","DOI":"10.1007\/3-540-45325-3_1"},{"key":"#cr-split#-42_CR3.2","unstructured":"Citations in this document:"},{"key":"42_CR4","doi-asserted-by":"publisher","first-page":"2010","DOI":"10.1109\/18.705584","volume":"44","author":"A.E. Ashikhmin","year":"1998","unstructured":"Ashikhmin, A.E., Barg, A.: Minimal vectors in linear codes. IEEE Transactions on Information Theory\u00a044, 2010\u20132017 (1998); Citations in this document:","journal-title":"IEEE Transactions on Information Theory"},{"key":"42_CR5","doi-asserted-by":"publisher","first-page":"1392","DOI":"10.1109\/18.771141","volume":"45","author":"A. Barg","year":"1999","unstructured":"Barg, A., Krouk, E.A., van Tilborg, H.C.A.: On the complexity of minimum distance decoding of long linear codes. IEEE Transactions on Information Theory\u00a045, 1392\u20131405 (1999); Citations in this document:","journal-title":"IEEE Transactions on Information Theory"},{"key":"42_CR6","doi-asserted-by":"crossref","unstructured":"Batten, L., Safavi-Naini, R. (eds.): Information security and privacy: 11th Australasian conference, ACISP 2006, Melbourne, Australia, July 3\u20135, 2006, proceedings. LNCS, vol.\u00a04058. Springer, Heidelberg (2006); See [43]","DOI":"10.1007\/11780656"},{"key":"42_CR7","volume-title":"Post-quantum cryptography","year":"2009","unstructured":"Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post-quantum cryptography. Springer, Heidelberg (2009); See [44]"},{"key":"#cr-split#-42_CR8.1","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Lange, T., Peters, C.: Attacking and defending the McEliece cryptosystem. In: PQCrypto 2008 [14], pp. 31???46 (2008), http:\/\/eprint.iacr.org\/2008\/318;","DOI":"10.1007\/978-3-540-88403-3_3"},{"key":"#cr-split#-42_CR8.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR9.1","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Lange, T., Peters, C.: Smaller decoding exponents: ball-collision decoding (full version) (2010), http:\/\/eprint.iacr.org\/2010\/585;","DOI":"10.1007\/978-3-642-22792-9_42"},{"key":"#cr-split#-42_CR9.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR10.1","unstructured":"Bernstein, D.J., Lange, T., Peters, C., van Tilborg, H.C.A.: Explicit bounds for generic decoding algorithms for code-based cryptography. In: WCC 2009 (2009);"},{"key":"#cr-split#-42_CR10.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR11.1","doi-asserted-by":"crossref","unstructured":"Berson, T.A.: Failure of the McEliece public-key cryptosystem under message-resend and related-message attack. In: Crypto ???97 [33], pp. 213???220 (1997);","DOI":"10.1007\/BFb0052237"},{"key":"#cr-split#-42_CR11.2","unstructured":"Citations in this document:"},{"key":"42_CR12","series-title":"Kluwer International Series in Engineering and Computer Science","volume-title":"Information, coding and mathematics","year":"2002","unstructured":"Blaum, M., Farrell, P.G., van Tilborg, H.C.A. (eds.): Information, coding and mathematics. Kluwer International Series in Engineering and Computer Science, vol.\u00a0687. Kluwer, Dordrecht (2002); See [53]"},{"key":"42_CR13","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1145\/322261.322269","volume":"28","author":"R.P. Brent","year":"1981","unstructured":"Brent, R.P., Kung, H.T.: The area-time complexity of binary multiplication. Journal of the ACM\u00a028, 521\u2013534 (1981), http:\/\/wwwmaths.anu.edu.au\/~brent\/pub\/pub055.html ; Citations in this document:","journal-title":"Journal of the ACM"},{"key":"42_CR14","doi-asserted-by":"crossref","unstructured":"Buchmann, J., Ding, J. (eds.): Post-quantum cryptography, second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17\u201319, 2008, proceedings. LNCS, vol.\u00a05299. Springer, Heidelberg (2008); see [8]","DOI":"10.1007\/978-3-540-88403-3"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"Camion, P., Charpin, P., Harari, S. (eds.): Eurocode \u201992: proceedings of the international symposium on coding theory and applications held in Udine, October 23\u201330, 1992. Springer, Heidelberg (1993); See [20]","DOI":"10.1007\/978-3-7091-2786-5"},{"key":"#cr-split#-42_CR16.1","unstructured":"Canteaut, A., Chabanne, H.: A further improvement of the work factor in an attempt at breaking McEliece???s cryptosystem. In: EUROCODE ???94 [21] (1994), http:\/\/www.inria.fr\/rrrt\/rr-2227.html;"},{"key":"#cr-split#-42_CR16.2","unstructured":"Citations in this document:"},{"key":"42_CR17","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, 367\u2013378 (1998), ftp:\/\/ftp.inria.fr\/INRIA\/tech-reports\/RR\/RR-2685.ps.gz ; Citations in this document:","journal-title":"IEEE Transactions on Information Theory"},{"key":"#cr-split#-42_CR18.1","doi-asserted-by":"crossref","unstructured":"Canteaut, A., Sendrier, N.: Cryptanalysis of the original McEliece cryptosystem. In: Asiacrypt ???98 [42], pp. 187???199 (1998);","DOI":"10.1007\/3-540-49649-1_16"},{"key":"#cr-split#-42_CR18.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR19.1","unstructured":"Chabanne, H., Courteau, B.: Application de la m??thode de d??codage it??rative d???Omura ?? la cryptanalyse du syst??me de McEliece. Universit?? de Sherbrooke, Rapport de Recherche, number 122 (1993);"},{"key":"#cr-split#-42_CR19.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR20.1","doi-asserted-by":"crossref","unstructured":"Chabaud, F.: Asymptotic analysis of probabilistic algorithms for finding short code-words. In: [15], pp. 175???183 (1993);","DOI":"10.1007\/978-3-7091-2786-5_15"},{"key":"#cr-split#-42_CR20.2","unstructured":"Citations in this document:"},{"key":"42_CR21","unstructured":"Charpin, P.(ed.): Livre des r\u00e9sum\u00e9 \u2014 EUROCODE \u201994. Abbaye de la Bussi\u00e8re sur Ouche, France, October 1994 (1994); See [16]"},{"key":"42_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-2174-1","volume-title":"Error-correcting coding for digital communication","author":"G.C. Clark Jr.","year":"1981","unstructured":"Clark Jr., G.C., Bibb Cain, J.: Error-correcting coding for digital communication. Plenum, New York (1981); Citations in this document:"},{"key":"42_CR23","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1109\/18.57202","volume":"35","author":"J.T. Coffey","year":"1990","unstructured":"Coffey, J.T., Goodman, R.M.: The complexity of information set decoding. IEEE Transactions on Information Theory\u00a035, 1031\u20131037 (1990); Citations in this document:","journal-title":"IEEE Transactions on Information Theory"},{"key":"42_CR24","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0166-218X(91)90107-8","volume":"33","author":"J.T. Coffey","year":"1991","unstructured":"Coffey, J.T., Goodman, R.M., Farrell, P.: New approaches to reduced complexity decoding. Discrete and Applied Mathematics\u00a033, 43\u201360 (1991); Citations in this document:","journal-title":"Discrete and Applied Mathematics"},{"key":"42_CR25","series-title":"LNCS","volume-title":"Coding Theory and Applications","year":"1989","unstructured":"Cohen, G.D., Wolfmann, J. (eds.): Coding theory and applications. LNCS, vol.\u00a0388. Springer, Heidelberg (1989); See [50]"},{"key":"42_CR26","first-page":"24","volume":"25","author":"I.I. Dumer","year":"1989","unstructured":"Dumer, I.I.: Two decoding algorithms for linear codes. Problemy Peredachi Informatsii\u00a025, 24\u201332 (1989); Citations in this document:","journal-title":"Problemy Peredachi Informatsii"},{"key":"#cr-split#-42_CR27.1","unstructured":"Dumer, I.I.: On minimum distance decoding of linear codes. In: [32], pp. 50???52 (1991);"},{"key":"#cr-split#-42_CR27.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR28.1","doi-asserted-by":"crossref","unstructured":"Finiasz, M., Sendrier, N.: Security bounds for the design of code-based cryptosystems. In: Asiacrypt 2009 [40] (2009), http:\/\/eprint.iacr.org\/2009\/414;","DOI":"10.1007\/978-3-642-10366-7_6"},{"key":"#cr-split#-42_CR28.2","unstructured":"Citations in this document:"},{"key":"42_CR29","unstructured":"Goldwasser, S. (ed.): Advances in cryptology|CRYPTO \u201988, proceedings of the conference on the theory and application of cryptography held at the University of California, Santa Barbara, California, August 21\u201325, 1988. LNCS, vol.\u00a0403. Springer, Heidelberg (1990); See [51]"},{"key":"42_CR30","unstructured":"G\u00fcnther, C.G. (ed.): Advances in cryptology \u2014 EUROCRYPT \u201988, proceedings of the workshop on the theory and application of cryptographic techniques held in Davos, May 25\u201327, 1988. LNCS, vol.\u00a0330. Springer, Heidelberg (1988); See [38]"},{"key":"42_CR31","doi-asserted-by":"crossref","unstructured":"Honary, B. (ed.): Cryptography and coding: proceedings of the 8th IMA international conference held in Cirencester, December 17\u201319. LNCS, vol.\u00a02260. Springer, Heidelberg (2001); See [3]","DOI":"10.1007\/3-540-45325-3"},{"key":"42_CR32","unstructured":"Kabatianskii, G.A. (ed.): Fifth joint Soviet-Swedish international workshop on information theory, Moscow, 1991 (1991); See [27]"},{"key":"42_CR33","doi-asserted-by":"crossref","unstructured":"Kaliski Jr., B.S. (ed.): Advances in cryptology \u2014 CRYPTO \u201997: 17th annual international cryptology conference, Santa Barbara, California, USA, August 17\u201321, 1997, proceedings. LNCS, vol.\u00a01294. Springer, Heidelberg (1997); See[11]","DOI":"10.1007\/BFb0052223"},{"key":"42_CR34","doi-asserted-by":"crossref","unstructured":"Kim, K. (ed.): Public key cryptography: proceedings of the 4th international workshop on practice and theory in public key cryptosystems (PKC 2001) held on Cheju Island, February 13\u201315, 2001. LNCS, vol.\u00a01992. Springer, Heidelberg (2001); See [36]","DOI":"10.1007\/3-540-44586-2"},{"key":"#cr-split#-42_CR35.1","doi-asserted-by":"crossref","unstructured":"Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thom??, E., Bos, J.W., Gaudry, P., Kruppa, A., Montgomery, P.L., Osvik, D.A., te Riele, H., Timofeev, A., Zimmermann, P.: Factorization of a 768-bit RSA modulus. In: Crypto 2010 [48], pp. 333???350 (2010), http:\/\/eprint.iacr.org\/2010\/006;","DOI":"10.1007\/978-3-642-14623-7_18"},{"key":"#cr-split#-42_CR35.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR36.1","doi-asserted-by":"crossref","unstructured":"Kobara, K., Imai, H.: Semantically secure McEliece public-key cryptosystems ??? conversions for McEliece PKC. In: PKC 2001 [34], pp. 19???35 (2001);","DOI":"10.1007\/3-540-44586-2_2"},{"key":"#cr-split#-42_CR36.2","unstructured":"Citations in this document:"},{"key":"42_CR37","first-page":"103","volume":"25","author":"E.A. Krouk","year":"1989","unstructured":"Krouk, E.A.: Decoding complexity bound for linear block codes. Problemy Peredachi Informatsii\u00a025, 103\u2013107 (1989); Citations in this document:","journal-title":"Problemy Peredachi Informatsii"},{"key":"#cr-split#-42_CR38.1","doi-asserted-by":"crossref","unstructured":"Lee, P.J., Brickell, E.F.: An observation on the security of McEliece???s public-key cryptosystem. In: Eurocrypt ???88 [30], pp. 275???280 (1988), http:\/\/dsns.csie.nctu.edu.tw\/research\/crypto\/HTML\/PDF\/E88\/275.PDF;","DOI":"10.1007\/3-540-45961-8_25"},{"key":"#cr-split#-42_CR38.2","unstructured":"Citations in this document:"},{"key":"42_CR39","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, 1354\u20131359 (1988); Citations in this document:","journal-title":"IEEE Transactions on Information Theory"},{"key":"42_CR40","doi-asserted-by":"crossref","unstructured":"Matsui, M. (ed.): Advances in cryptology \u2014 ASIACRYPT 2009, 15th international conference on the theory and application of cryptology and information security, Tokyo, Japan, December 6\u201310, 2009, proceedings. LNCS, vol.\u00a05912. Springer, Heidelberg (2009); See [28]","DOI":"10.1007\/978-3-642-10366-7"},{"key":"#cr-split#-42_CR41.1","unstructured":"McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. JPL DSN Progress Report 114???116 (1978), http:\/\/ipnpr.jpl.nasa.gov\/progress_report2\/42-44\/44N.PDF;"},{"key":"#cr-split#-42_CR41.2","unstructured":"Citations in this document:"},{"key":"42_CR42","doi-asserted-by":"crossref","unstructured":"Ohta, K., Pei, D. (eds.): Advances in cryptology \u2014 ASIACRYPT\u201998: proceedings of the international conference on the theory and application of cryptology and information security held in Beijing. LNCS, vol.\u00a01514. Springer, Heidelberg (1998); See [18]","DOI":"10.1007\/3-540-49649-1"},{"key":"#cr-split#-42_CR43.1","doi-asserted-by":"crossref","unstructured":"Overbeck, R.: Statistical decoding revisited. In: ACISP 2006 [6], pp. 283???294 (2006);","DOI":"10.1007\/11780656_24"},{"key":"#cr-split#-42_CR43.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR44.1","doi-asserted-by":"crossref","unstructured":"Overbeck, R., Sendrier, N.: Code-based cryptography. In: [7], pp. 95???145 (2009);","DOI":"10.1007\/978-3-540-88702-7_4"},{"key":"#cr-split#-42_CR44.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR45.1","doi-asserted-by":"crossref","unstructured":"Peters, C.: Information-set decoding for linear codes over F q . In: Post-Quantum Cryptography [49], pp. 81???94 (2010);","DOI":"10.1007\/978-3-642-12929-2_7"},{"key":"#cr-split#-42_CR45.2","unstructured":"Citations in this document:"},{"key":"42_CR46","unstructured":"Pomerance, C. (ed.): Advances in cryptology \u2014 CRYPTO \u201987, proceedings of the conference on the theory and applications of cryptographic techniques held at the University of California, Santa Barbara, California, August 16\u201320, 1987. LNCS, vol.\u00a0293. Springer, Heidelberg (1987), http:\/\/dsns.csie.nctu.edu.tw\/research\/crypto\/HTML\/PDF\/C87\/224.PDF ; See [1]"},{"key":"#cr-split#-42_CR47.1","doi-asserted-by":"crossref","unstructured":"Prange, E.: The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory IT-8, S5???S9 (1962);","DOI":"10.1109\/TIT.1962.1057777"},{"key":"#cr-split#-42_CR47.2","unstructured":"Citations in this document:"},{"key":"42_CR48","unstructured":"Rabin, T. (ed.): Advances in cryptology \u2014 CRYPTO 2010, 30th annual cryptology conference, Santa Barbara, CA, USA, August 15\u201319, 2010, proceedings. LNCS, vol.\u00a06223. Springer, Heidelberg (2010); See [35]"},{"key":"42_CR49","doi-asserted-by":"crossref","unstructured":"Sendrier, N. (ed.): Post-quantum cryptography, third international workshop, PQCrypto, Darmstadt, Germany, May 25\u201328, 2010, proceedings. LNCS, vol.\u00a06061. Springer, Heidelberg (2010); See [45]","DOI":"10.1007\/978-3-642-12929-2"},{"key":"#cr-split#-42_CR50.1","doi-asserted-by":"crossref","unstructured":"Stern, J.: A method for finding codewords of small weight. In: [25], pp. 106???113 (1989);","DOI":"10.1007\/BFb0019850"},{"key":"#cr-split#-42_CR50.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR51.1","doi-asserted-by":"crossref","unstructured":"van Tilburg, J.: On the McEliece public-key cryptosystem. In: Crypto ???88 [29], pp. 119???131 (1990);","DOI":"10.1007\/0-387-34799-2_10"},{"key":"#cr-split#-42_CR51.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR52.1","unstructured":"van Tilburg, J.: Security-analysis of a class of cryptosystems based on linear error-correcting codes. Ph.D. thesis, Technische Universiteit Eindhoven (1994);"},{"key":"#cr-split#-42_CR52.2","unstructured":"Citations in this document:"},{"key":"#cr-split#-42_CR53.1","doi-asserted-by":"crossref","unstructured":"Verheul, E.R., Doumen, J.M., van Tilborg, H.C.A.: Sloppy Alice attacks! Adaptive chosen ciphertext attacks on the McEliece public-key cryptosystem. In: [12], pp. 99???119 (2002);","DOI":"10.1007\/978-1-4757-3585-7_7"},{"key":"#cr-split#-42_CR53.2","unstructured":"Citations in this document:"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22792-9_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T07:27:30Z","timestamp":1741418850000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22792-9_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642227912","9783642227929"],"references-count":77,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22792-9_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}