{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T11:52:37Z","timestamp":1775044357860,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,2,3]],"date-time":"2015-02-03T00:00:00Z","timestamp":1422921600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s10623-015-0036-z","type":"journal-article","created":{"date-parts":[[2015,2,2]],"date-time":"2015-02-02T03:21:12Z","timestamp":1422847272000},"page":"87-112","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Structural cryptanalysis of McEliece schemes with compact keys"],"prefix":"10.1007","volume":"79","author":[{"given":"Jean-Charles","family":"Faug\u00e8re","sequence":"first","affiliation":[]},{"given":"Ayoub","family":"Otmani","sequence":"additional","affiliation":[]},{"given":"Ludovic","family":"Perret","sequence":"additional","affiliation":[]},{"given":"Fr\u00e9d\u00e9ric","family":"de Portzamparc","sequence":"additional","affiliation":[]},{"given":"Jean-Pierre","family":"Tillich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,3]]},"reference":[{"key":"36_CR1","unstructured":"Baldi M., Bianchi M., Chiaraluce F.: Security and complexity of the McEliece cryptosystem based on QC-LDPC codes. IET Inf. Secur. 7(3), 212\u2013220 (2013). See also arXiv:1109.5827v6 [cs.CR]"},{"key":"36_CR2","doi-asserted-by":"crossref","unstructured":"Baldi M., Bodrato M., Chiaraluce F.: A new analysis of the McEliece cryptosystem based on QC-LDPC codes. In: Proceedings of the 6th International Conference on Security and Cryptography for Networks SCN \u201908, pp. 246\u2013262. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-85855-3_17"},{"key":"36_CR3","doi-asserted-by":"crossref","unstructured":"Barbier M.: Key reduction of McEliece\u2019s cryptosystem using list decoding. CoRR, arXiv:1102.2566 (2011)","DOI":"10.1109\/ISIT.2011.6034058"},{"key":"36_CR4","doi-asserted-by":"crossref","unstructured":"Barreto P.S.L.M., Cayrel P.-L., Misoczki R., Niebuhr R.: Quasi-dyadic CFS signatures. In: Lai X., Yung M., Lin D. (eds.) Inscrypt. Lecture Notes in Computer Science, vol. 6584, pp. 336\u2013349. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-21518-6_23"},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"Barreto P.S.L.M., Lindner R., Misoczki R.: Monoidic codes in cryptography. In: Yang B.Y. (ed.) PQCrypto. Lecture Notes in Computer Science, vol. 7071, pp. 179\u2013199. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-25405-5_12"},{"key":"36_CR6","doi-asserted-by":"crossref","unstructured":"Becker A., Joux A., May A., Meurer A.: Decoding random binary linear codes in $$2^{n\/20}$$ 2 n \/ 20 : how 1 + 1 = 0 improves information set decoding. In: Pointcheval D., Johansson T. (eds.) EUROCRYPT. Lecture Notes in Computer Science, vol. 7237, pp. 520\u2013536. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-29011-4_31"},{"key":"36_CR7","doi-asserted-by":"crossref","unstructured":"Berger T.P.: Cyclic alternant codes induced by an automorphism of a GRS code. In: Mullin R., Mullen G. (eds.) Finite Fields: Theory, Applications and Algorithms. Contemporary Mathematics, vol. 225, pp. 143\u2013154. AMS, Waterloo, Canada (1999)","DOI":"10.1090\/conm\/225\/03216"},{"key":"36_CR8","doi-asserted-by":"crossref","unstructured":"Berger T.P.: Goppa and related codes invariant under a prescribed permutation. IEEE Trans. Inf. Theory 46(7), 2628 (2000)","DOI":"10.1109\/18.887871"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"Berger T.P.: On the cyclicity of Goppa codes, parity-check subcodes of Goppa codes and extended Goppa codes. Finite Fields Appl. 6, 255\u2013281 (2000)","DOI":"10.1006\/ffta.2000.0277"},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"Berger T.P., Cayrel P.L., Gaborit P., Otmani A.L.: Reducing key length of the McEliece cryptosystem. In: Preneel B. (ed.) Progress in Cryptology\u2014Second International Conference on Cryptology in Africa (AFRICACRYPT 2009). Lecture Notes in Computer Science, vol. 5580, pp. 77\u201397, 21\u201325 June 2009, Gammarth, Tunisia","DOI":"10.1007\/978-3-642-02384-2_6"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"Bernstein D.J., Lange T., Peters C.: Attacking and defending the McEliece cryptosystem. In : PQCrypto. Lecture Notes in Computer Science, vol. 5299. pp. 31\u201346. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-88403-3_3"},{"key":"36_CR12","doi-asserted-by":"crossref","unstructured":"Bernstein D.J., Lange T., Peters C.: Attacking and defending the McEliece cryptosystem. In: PQCrypto, pp. 31\u201346. (2008)","DOI":"10.1007\/978-3-540-88403-3_3"},{"key":"36_CR13","unstructured":"Bernstein D.J., Lange T., Peters C., van Tilborg H.: Explicit bounds for generic decoding algorithms for code-based cryptography. In: Pre-proceedings of WCC 2009, pp. 168\u2013180 (2009)"},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"Bernstein D.J., Lange T., Peters C.: Smaller decoding exponents: ball-collision decoding. In: Phillip R. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 6841, pp. 743\u2013760. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-22792-9_42"},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"Bosma W., Cannon J.J., Playoust C.: The Magma algebra system I: the user language. J. Symb. Comput. 24(3\u20134), 235\u2013265 (1997)","DOI":"10.1006\/jsco.1996.0125"},{"key":"36_CR16","unstructured":"Buchberger B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Innsbruck (1965)"},{"key":"36_CR17","doi-asserted-by":"crossref","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 Trans. Inf. Theory 44(1), 367\u2013378 (1998)","DOI":"10.1109\/18.651067"},{"key":"36_CR18","unstructured":"Cox D.A., Little J.B., O\u2019Shea D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York (2001)"},{"key":"36_CR19","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re J.-C.: A new efficient algorithm for computing Gr\u00f6bner bases (F4). J. Pure Appl. Algebra 139(1\u20133), 61\u201388 (1999)","DOI":"10.1016\/S0022-4049(99)00005-5"},{"key":"36_CR20","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re J.-C.: A new efficient algorithm for computing Gr\u00f6bner bases without reduction to zero: F5. In: ISSAC\u201902, pp. 75\u201383. ACM Press, New York (2002)","DOI":"10.1145\/780506.780516"},{"key":"36_CR21","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re, J.-C.: FGb: a library for computing Gr\u00f6bner bases. In: Fukuda K., Hoeven J., Joswig M., Takayama N. (eds.) Mathematical Software\u2014ICMS 2010. Lecture Notes in Computer Science, vol. 6327, pp. 84\u201387. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-15582-6_17"},{"key":"36_CR22","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re J.-C., Gauthier V., Otmani A., Perret L., Tillich J.-P.: A distinguisher for high rate McEliece cryptosystems. IEEE Trans. Inf. Theory 59(10), 6830\u20136844 (2013)","DOI":"10.1109\/TIT.2013.2272036"},{"key":"36_CR23","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re J.-C., Gauthier-Umana V., Otmani A., Perret L., Tillich J.-P.: A distinguisher for high rate McEliece cryptosystems. In: Information Theory Workshop (ITW), 2011 IEEE, pp. 282\u2013286 (2011)","DOI":"10.1109\/ITW.2011.6089437"},{"key":"36_CR24","unstructured":"Faug\u00e8re J.-C., Otmani A., Perret L., de Portzamparc F., Tillich J.-P.: Folding alternant and Goppa codes with non-trivial automorphism groups. (2014). arXiv:1405.5101 [cs.IT]"},{"key":"36_CR25","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re J.-C., Otmani A., Perret L., de Portzamparc L., Tillich J.-P.: Structural weakness of compact variants of the McEliece cryptosystem. In: Proceedings of the IEEE International Symposium Information Theory\u2014ISIT 2014, Honolulu, HI, USA, pp. 1717\u20131721 (2014)","DOI":"10.1109\/ISIT.2014.6875127"},{"key":"36_CR26","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re J.-C., Otmani A., Perret L., Tillich J.-P.: Algebraic cryptanalysis of McEliece variants with compact keys. In: Gilbert H. (ed.) Advances in Cryptology\u2014EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30\u2013June 3, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6110, pp. 279\u2013298. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-13190-5_14"},{"key":"36_CR27","unstructured":"Faug\u00e8re J.-C., Otmani A., Perret L., Tillich J.-P.: Algebraic cryptanalysis of McEliece variants with compact keys\u2014toward a complexity analysis. In: SCC \u201910: Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography, pp. 45\u201355. RHUL (2010)"},{"key":"36_CR28","doi-asserted-by":"crossref","unstructured":"Finiasz M., Sendrier N.: Security bounds for the design of code-based cryptosystems. In: Matsui M. (ed.) Asiacrypt 2009. Lecture Notes in Computer Science, vol. 5912, pp. 88\u2013105. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-10366-7_6"},{"key":"36_CR29","unstructured":"Gaborit P.: Shorter keys for code based cryptography. In: Proceedings of the 2005 International Workshop on Coding and Cryptography (WCC 2005), Bergen, Norway, pp. 81\u201391 (2005)"},{"key":"36_CR30","unstructured":"Gauthier U.V., Leander G.: Practical key recovery attacks on two McEliece variants. In: International Conference on Symbolic Computation and Cryptography-SCC, vol. 2010, p. 62 (2010)"},{"key":"36_CR31","doi-asserted-by":"crossref","unstructured":"Gilbert H., (ed.) Advances in Cryptology\u2014EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30\u2013June 3, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6110. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-13190-5"},{"key":"36_CR32","doi-asserted-by":"crossref","unstructured":"Heyse S.: Implementation of McEliece based on quasi-dyadic Goppa codes for embedded devices. In: Yang B.-Y. (ed.) Post-quantum Cryptography. Lecture Notes in Computer Science, vol. 7071, pp. 143\u2013162. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-25405-5_10"},{"key":"36_CR33","doi-asserted-by":"crossref","unstructured":"Lee P.J., Brickell E.F.: An observation on the security of McEliece\u2019s public-key cryptosystem. In: Advances in Cryptology\u2014EUROCRYPT\u201988. Lecture Notes in Computer Science, vol. 330\/1988, pp. 275\u2013280. Springer, Berlin (1988)","DOI":"10.1007\/3-540-45961-8_25"},{"key":"36_CR34","doi-asserted-by":"crossref","unstructured":"Leon J.S.: A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Trans. Inf. Theory 34(5), 1354\u20131359 (1988)","DOI":"10.1109\/18.21270"},{"key":"36_CR35","doi-asserted-by":"crossref","unstructured":"Loidreau P., Sendrier N.: Weak keys in the McEliece public-key cryptosystem. IEEE Trans. Inf. Theory 47(3), 1207\u20131211 (2001)","DOI":"10.1109\/18.915687"},{"key":"36_CR36","unstructured":"Loidreau P.: On cellular code and their cryptographic applications. In: Landjev I., Kabatiansky G. (eds.) Proceedings of ACCT14 (Algebraic and Combinatorial Coding Theory). Svetlogorsk, Russia (2014)"},{"key":"36_CR37","doi-asserted-by":"crossref","unstructured":"L\u00f6ndahl C., Johansson T., Koochak Shooshtari M., Ahmadian-Attari M., Reza Aref M.: A New Attack on McEliece Public-Key Cryptosystems Using Quasi-cyclic Codes of Even Dimension (preprint) (2014)","DOI":"10.1007\/s10623-015-0099-x"},{"key":"36_CR38","doi-asserted-by":"crossref","unstructured":"Lyubashevsky L., Peikert C., Regev O.: On ideal lattices and learning with errors over rings. In: Gilbert H. (ed.) Advances in Cryptology\u2014EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30\u2013June 3, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6110, pp. 1\u201323. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"36_CR39","unstructured":"MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes, 5th edn. Amsterdam, North-Holland (1986)"},{"key":"36_CR40","doi-asserted-by":"crossref","unstructured":"May A., Meurer A., Thomae E.: Decoding random linear codes in $$\\tilde{O}(2^{0.054n})$$ O ~ ( 2 0.054 n ) . In: Lee D.H., Wang X. (eds.) ASIACRYPT. Lecture Notes in Computer Science, vol. 7073, pp. 107\u2013124. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-25385-0_6"},{"key":"36_CR41","unstructured":"McEliece R.J.: A Public-Key System Based on Algebraic Coding Theory, pp. 114\u2013116. Jet Propulsion Lab. DSN Progress Report 44 (1978)"},{"key":"36_CR42","doi-asserted-by":"crossref","unstructured":"Misoczki R., Barreto P.S.L.M.: Compact McEliece keys from Goppa codes. In: Selected Areas in Cryptography (SAC 2009). Calgary, Canada, 13\u201314 August 2009","DOI":"10.1007\/978-3-642-05445-7_24"},{"key":"36_CR43","doi-asserted-by":"crossref","unstructured":"Misoczki R., Barreto P.S.L.M.: Compact McEliece keys from Goppa codes. IACR Cryptology ePrint Archive, 2009:187 (2009)","DOI":"10.1007\/978-3-642-05445-7_24"},{"key":"36_CR44","doi-asserted-by":"crossref","unstructured":"Patterson N.: The algebraic decoding of Goppa codes. IEEE Trans. Inf. Theory 21(2), 203\u2013207 (1975)","DOI":"10.1109\/TIT.1975.1055350"},{"key":"36_CR45","doi-asserted-by":"crossref","unstructured":"Persichetti E.: Compact McEliece keys based on quasi-dyadic Srivastava codes. J. Math. Cryptol. 6(2), 149\u2013169 (2012)","DOI":"10.1515\/jmc-2011-0099"},{"key":"36_CR46","doi-asserted-by":"crossref","unstructured":"Peters C.: Information-set decoding for linear codes over F $$_{\\text{ q }}$$ q . In: Nicolas S. (ed.) PQCrypto. Lecture Notes in Computer Science, vol. 6061, pp. 81\u201394. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-12929-2_7"},{"key":"36_CR47","doi-asserted-by":"crossref","unstructured":"Sendrier N.: Finding the permutation between equivalent linear codes: the support splitting algorithm. IEEE Trans. Inf. Theory 46(4), 1193\u20131203 (2000)","DOI":"10.1109\/18.850662"},{"key":"36_CR48","doi-asserted-by":"crossref","unstructured":"Stehl\u00e9 D., Steinfeld R., Tanaka K., Xagawa K.: Efficient public key encryption based on ideal lattices. In: Matsui M. (ed.) ASIACRYPT. Lecture Notes in Computer Science, vol. 5912, pp. 617\u2013635. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-10366-7_36"},{"key":"36_CR49","doi-asserted-by":"crossref","unstructured":"Stern J.: A method for finding codewords of small weight. In: Cohen G.D., Wolfmann J. (eds.) Coding Theory and Applications. Lecture Notes in Computer Science, vol. 388, pp. 106\u2013113. Springer, Heidelberg (1988)","DOI":"10.1007\/BFb0019850"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-015-0036-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10623-015-0036-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-015-0036-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T11:57:21Z","timestamp":1566302241000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10623-015-0036-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,3]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["36"],"URL":"https:\/\/doi.org\/10.1007\/s10623-015-0036-z","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,3]]}}}