Overview of the Mceliece Cryptosystem and its Security

[1] AVANZI, R.-HOERDER, S.-PAGE, D.-TUNSTALL, M.: Side-channel attacks on the McEliece and Niederreiter public-key cryptosystems, J. Cryptogr. Eng. 1 (2011), 271-281.10.1007/s13389-011-0024-9Search in Google Scholar

[2] BALDI, M.-BODRATO, M.-CHIARALUCE, F.: A new analysis of the McEliece cryptosystem based on QC-LDPC codes, in: Proc. of the 6th Internat. Conf.-SCN ’08, Amalfi, Italy, 2008 (R. Ostrovsky et al., eds.), Lecture Notes in Comput. Sci., Vol. 5229, Springer, Berlin, 2008, pp. 246-262.Search in Google Scholar

[3] BECKER, A.-JOUX, A.-MAY, A.-MEURER, A.: Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves information set decoding, in: Advances in Cryptology-EUROCRYPT ’12, 31st Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques, Cambridge, UK, 2012 (D. Pointcheval et al., eds.), Lecture Notes in Comput. Sci., Vol. 7237, Springer, Berlin, 2012, pp. 520-536.Search in Google Scholar

[4] BERLEKAMP, E.-MCELIECE, R.-VAN TILBORG, H.: On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory 24 (1978), 384-386.10.1109/TIT.1978.1055873Search in Google Scholar

[5] BERNSTEIN, D. J.: List decoding for binary Goppa codes, in: Coding and Cryptology, 3rd Internat. Workshop-IWCC ’11, Qingdao, China, 2011 (Y. M. Chee et al., eds.), Lecture Notes in Comput. Sci., Vol. 6639, Springer, Berlin, 2011, 62-80.Search in Google Scholar

[6] BERNSTEIN, D. J.-LANGE, T.-PETERS, C.: Attacking and defending the McEliece cryptosystem, in: Post-Quantum Cryptography, 2nd Internat. Workshop-PQCrypto ’08 (J. Buchmann et al., eds.), Cincinnati, OH, USA, 2008, Lecture Notes in Comput. Sci., Vol. 5299, Springer, Berlin, 2008, pp. 31-46.Search in Google Scholar

[7] BERNSTEIN, D. J.-LANGE, T.-PETERS, C.: Smaller decoding exponents: Ball-collision decoding, in: Advances in Cryptology-CRYPTO ’11, 31st Annual Cryptology Conf., Santa Barbara, CA, USA, 2011, (P. Rogaway, ed.), Lecture Notes in Comput. Sci., Vol. 6841, Springer, Berlin, 2011, pp. 743-760.Search in Google Scholar

[8] BERNSTEIN, D. J.-LANGE, T.-PETERS, C.: Wild McEliece, in: Selected Areas in Cryptography, 17th Internat. Workshop-SAC ’10, Waterloo, Ontario, Canada, 2010 (A. Biryukov et al., eds.), Lecture Notes in Comput. Sci., Vol. 6544, Springer, Berlin, 2011, pp. 143-158.Search in Google Scholar

[9] BERNSTEIN, D. J.-LANGE, T.-PETERS, C.: Wild McEliece incognito, in: Post- -Quantum Cryptography, 4th Internat. Workshop-PQCrypto ’11, Taipei, Taiwan, 2011 (B.-Y. Yang, ed.), Lecture Notes in Comput. Sci., Vol. 7071, Springer, Berlin, 2011, 244-25410.1007/978-3-642-25405-5_16Search in Google Scholar

[10] BERSON, T. A.: Failure of the McEliece public-key cryptosystem under message-resend and related-message attack, in: Advances in Cryptology-CRYPTO ’97, 17th Annual Internat. Cryptology Conf. Santa Barbara, CA, USA, 1997 (B. S. Kaliski, jr. ed.), Lecture Notes in Comput. Sci., Vol. 1294, Springer, Berlin, 1997, pp. 213-220.Search in Google Scholar

[11] BISWAS, B.-HERBERT, V.: Efficient root finding of polynomials over fields of characteristic 2, in: Western European Workshop on Research in Cryptology-WEWORC ’09, Graz, Austria, 2009 (C. Rechberger, ed.), Lecture Notes in Comput. Sci., Vol. 6429, Springer-Verlag, Berlin, 2009.Search in Google Scholar

[12] BISWAS, B.-SENDRIER, N.: McEliece cryptosystem implementation: theory and practice, in: Post-Quantum Cryptography, 2nd Internat. Workshop-PQCrypto ’08, Cincinnati, OH, USA, 2008 (J. Buchmann et al., eds.), Lecture Notes in Comput. Sci., Vol. 5299, Springer, Berlin, 2008, pp. 47-62.Search in Google Scholar

[13] CANTEAUT, A.-CHABAUD, F.: A new algorithm for finding minimum-weight words in a linear code: application to McElieces cryptosystem and to narrow-sense BCH codes of length 511. IEEE Trans. Inform. Theory 44 (1998), 367-378.Search in Google Scholar

[14] CANTEAUT, A.-SENDRIER, N.: Cryptanalysis of the original McEliece cryptosystem, in: Advances in Cryptology-ASIACRYPT ’98, Internat. Conf. on the Theory and Application of Cryptology and Inform. Security, Beijing, China, 1998 (K. Ohta et al., eds.), Lecture Notes in Comput. Sci., Vol. 1514, Springer, Berlin, 1998, pp. 187-199.Search in Google Scholar

[15] CHEN, C.-EISENBARTH, T.-VON MAURICH, I.-STEINWANDT, R.: Differential power analysis of a McEliece cryptosystem. Cryptology ePrint Archive, Report 2014/534, 2014, http://eprint.iacr.org/.Search in Google Scholar

[16] COURTOIS, N. T.-FINIASZ, M.-SENDRIER, N.: How to achieve a mceliece-based digital signature scheme, in: Advances in Cryptology-ASIACRYPT ’01, 7th Internat. Conf. on the Theory and Appl. of Cryptology and Inform. Security, Gold Coast, Australia, 2001 (C. Boyd, ed.), Lecture Notes in Comput. Sci., Vol. 2248, Springer, Berlin, 2001, pp. 157-174.Search in Google Scholar

[17] COUVREUR, A.-OTMANI, A.-TILLICH, J.-P.: Polynomial time attack on wild McEliece over quadratic extensions, Cryptology ePrint Archive, Report 2014/112, 2014, http://eprint.iacr.org/.10.1007/978-3-642-55220-5_2Search in Google Scholar

[18] DÖTTLING, N.-DOWSLEY, R.-M¨ULLER-QUADE, J.-NASCIMENTO, A. C. A.: A CCA2 secure variant of the McEliece cryptosystem. IEEE Trans. Inform. Theory 58 (2012), 6672-6680.Search in Google Scholar

[19] EISENBARTH, T.-G¨UNEYSU, T.-HEYSE, S.-PAAR, C.: MicroEliece : McEliece for embedded devices, in: Cryptographic Hardware and Embedded Systems-CHES ’09, 11th Internat. Workshop Lausanne, Switzerland, 2009 (Ch. Clavier et al., eds.), Lecture Notes in Comput. Sci., Vol. 5747, Springer, Berlin, 2009, pp. 49-64.Search in Google Scholar

[20] ENGELBERT, D.-OVERBECK, R.-SCHMIDT, A.: A summary of McEliece-type cryptosystems and their security, J. Math. Cryptol. 1 (2007), 151-199.10.1515/JMC.2007.009Search in Google Scholar

[21] FAUGÈRE, J.-C.-GAUTHIER-UMA˜NA,V.-OTMANI, A.-PERRET, L.-TILLICH, J.-P.: A distinguisher for high-rate McEliece cryptosystems, IEEE Trans. Inform. Theory 59 (2013), 6830-6844.10.1109/TIT.2013.2272036Search in Google Scholar

[22] FAUGÈRE, J.-C.-OTMANI, A.-PERRET, L.-DE PORTZAMPARC, L.-TILLICH: Folding alternant and Goppa codes with non-trivial automorphism groups, arXiv preprint arXiv:1405.5101, 2014.Search in Google Scholar

[23] FAUGÈRE, J.-C.-OTMANI, A.-PERRET, L.-DE PORTZAMPARC, F.-TILLICH, J.-P.: Structural cryptanalysis of McEliece schemes with compact keys, Cryptology ePrint Archive, Report 2014/210, 2014, http://eprint.iacr.org/ Search in Google Scholar

[24] FAUGÈRE, J.-C.-OTMANI, A.-PERRET, L.-TILLICH, J.-P.: Algebraic cryptanalysis of McEliece variants with compact keys, in: Advances in Cryptology-EUROCRYPT ’10, 29th Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques, French Riviera, 2010 (H. Gilbert, ed.), Lecture Notes in Comput. Sci., Vol. 6110, Springer, Berlin, 2010, pp. 279-298.Search in Google Scholar

[25] FUJISAKI, E.-OKAMOTO, T.: Secure integration of asymmetric and symmetric encryption schemes, in: Advances in Cryptology-CRYPTO ’99, 19th Annual Internat. Cryptology Conf. Santa Barbara, CA, USA, 1999 (M. Wiener, ed.), Lecture Notes in Comput. Sci., Vol. 1666, Springer, Berlin, 1999, pp. 537-554.Search in Google Scholar

[26] GALLAGER, R. G.: Low-density parity-check codes, IRE Trans. Inform. Theory 8 (1962), 21-28.10.1109/TIT.1962.1057683Search in Google Scholar

[27] GLIGOROSKI, D.-SAMARDJISKA, S.-JACOBSEN, H.-BEZZATEEV, S.: McEliece in the world of Escher, Cryptology ePrint Archive, Report 2014/360, 2014, http://eprint.iacr.org/.Search in Google Scholar

[28] GOPPA, V. D.: A new class of linear error correcting codes, Probl. Pered. Inform. 6 (1970), 24-30.Search in Google Scholar

[29] HALL, C.-GOLDBERG, I.-SCHNEIER, B.: Reaction attacks against several publickey cryptosystem, in: Information and Commun. Security, 2nd Internat. Conf.-ICICS ’99, Sydney, Australia, 1999 (V. Varadharajan et al., eds.), Lecture Notes in Comput. Sci., Vol. 1726, Springer, Berlin, 1999, pp. 2-12.Search in Google Scholar

[30] HAMDAOUI, Y.-SENDRIER, N.: A non asymptotic analysis of information set decoding, IACR Cryptology ePrint Archive, 2013:162, 2013.Search in Google Scholar

[31] HEYSE, S.-MORADI, A.-PAAR, C.: Practical power analysis attacks on software implementations of McEliece, in: Post-Quantum Cryptography, 3rd Internat. Workshop- -PQCrypto ’10, Darmstadt, Germany, 2010 (N. Sendrier, ed.), Lecture Notes in Comput. Sci., Vol. 6061, Springer, Berlin, 2010, pp. 108-125.Search in Google Scholar

[32] HEYSE, S.-VON MAURICH, I.-G¨UNEYSU, T.: Smaller keys for code-based cryptography: QC-MDPC McEliece implementations on embedded devices, in: Cryptographic Hardware and Embedded Systems-CHES ’13 15th Internat. Workshop, Santa Barbara, CA, USA, 2013, (G. Bertoni and J.-S. Coron, eds.), Lecture Notes in Comput. Sci., Vol. 8086, Springer, Berlin, 2013, pp. 273-292.Search in Google Scholar

[33] KOBARA, K.-IMAI, H.: Semantically secure McEliece public-key cryptosystems- -conversions for McEliece PKC, in: Public Key Cryptography, 4th Internat. Workshop on Practice and Theory in Public Key Cryptosystems-PKC ’01, Cheju Island, Korea, 2001 (K. Kim, ed.), Lecture Notes in Comput. Sci., Vol. 1992, Springer, Berlin, 2001, pp. 19-35.Search in Google Scholar

[34] LEE, P. J.-BRICKELL, E. F.: An observation on the security of McElieces public-key cryptosystem, in: Advances in cryptology-EUROCRYPT 88, Workshop on the Theory and Appl. of Cryptogr. Techniques, Davos, Switzerland, 1988 (D. Barstow et al., eds.), Lecture Notes in Comput. Sci., Vol. 330, Springer, Berlin, 1988, pp. 275-280.10.1007/3-540-45961-8_25Search in Google Scholar

[35] LEON, J.: A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Trans. Inform. Theory 34 (1988), 1354-1359.10.1109/18.21270Search in Google Scholar

[36] MAY, A.-MEURER, A.-THOMAE, E.: Decoding random linear codes in O(20.054n), in: Advances in Cryptology-ASIACRYPT ’11, 7th Internat. Conf. on the Theory and Appl. of Cryptology and Inform. Security, Seoul, South Korea, 2011 (D. H. Lee and X. Wang, eds.), Lecture Notes in Computer Science, Vol. 7073, Springer, Berlin, 2011, pp. 107-124.Search in Google Scholar

[37] MCELIECE, R. J.: A public-key cryptosystem based on algebraic coding theory, DSN Progress Report 42 (1978), 114-116 Search in Google Scholar

[38] MISOCZKI, R.-TILLICH, J.-P.-SENDRIER, N.-BARRETO, P. S. L. M.: MDPCMcEliece: New McEliece variants from moderate density parity-check codes, in: IEEE Internat. Symposium on Information Theory-ISIT ’13, Istanbul, Turkey, 2013, IEEE, 2013, pp. 2069-2073.10.1109/ISIT.2013.6620590Search in Google Scholar

[39] MONICO, C.-ROSENTHAL, J.-SHOKROLLAHI, A.: Using low density parity check codes in the McEliece cryptosystem, in: IEEE Internat. Symposium on Information Theory, Sorrento, Italy, 2000, IEEE, 2000, p. 215.Search in Google Scholar

[40] NIEBUHR, R.-MEZIANI, M.-BULYGIN, S.-BUCHMANN, J.: Selecting parameters for secure McEliece-based cryptosystems, Int. J. Inf. Sec. 11 (2012), 137-147.10.1007/s10207-011-0153-2Search in Google Scholar

[41] NIEDERREITER, H.: Knapsack-type cryptosystems and algebraic coding theory, Probl. Control Inf. Theory 15 (1986), 159-166.Search in Google Scholar

[42] NOJIMA, R.-IMAI, H.-KOBARA, K.-MOROZOV, K.: Semantic security for the McEliece cryptosystem without random oracles, Des. Codes Cryptography 49 (2008), 289-305.10.1007/s10623-008-9175-9Search in Google Scholar

[43] OTMANI, A.-TILLICH, J.-P.-DALLOT, L.: Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes, Math. Comput. Sci. 3 (2010), 129-140.10.1007/s11786-009-0015-8Search in Google Scholar

[44] OVERBECK, R.: An analysis of side channels in the McEliece PKC (2008), www.cosic.esat.kuleuven.be/nato_arw/slides_participants/Overbeck\slides_nato08.pdf.Search in Google Scholar

[45] OVERBECK, R.-SENDRIER, N.: Code-based cryptography, in: Post-Quantum Cryptography, 1st Internat. Workshop-PQCrypto ’06, Leuven, The Netherland, 2006 (D. Bernstein et al., eds.), Springer, Berlin, 2009, pp. 95-145.10.1007/978-3-540-88702-7_4Search in Google Scholar

[46] PATTERSON, N. J.: The algebraic decoding of Goppa codes, IEEE Trans. Inform. Theory 21 (1975), 203-207.10.1109/TIT.1975.1055350Search in Google Scholar

[47] PERSICHETTI, E.: On a CCA2-secure variant of McEliece in the standard model, IACR Cryptology ePrint Archive, 2012:268, 2012.Search in Google Scholar

[48] PETERS, C.: Information-set decoding for linear codes over Fq, in: Post-Quantum Cryptography, 3rd Internat. Workshop-PQCrypto ’10, Darmstadt, Germany, 2010 (N. Sendrier, ed.), Lecture Notes in Comput. Sci., Vol. 6061, Springer, Berlin, 2010, pp. 81-94.Search in Google Scholar

[49] POINTCHEVAL, D.: Chosen-ciphertext security for any one-way cryptosystem, in: Public Key Cryptography-PKC ’00, 3rd Internat. Workshop on Practice and Theory in Public Key Cryptosystems, Melbourne, Victoria, Australia, 2000 (H. Imai et al., eds.), Lecture Notes in Comput. Sci., Vol. 1751, Springer, Berlin, 2000, pp. 129-146.Search in Google Scholar

[50] REPKA, M.-CAYREL, P.-L.: Cryptography based on error correcting codes: a survey, in: Multidisciplinary Perspectives in Cryptology and Information Security, IGI Global, 2014, pp. 133-156.10.4018/978-1-4666-5808-0.ch005Search in Google Scholar

[51] SENDRIER, N.: Finding the permutation between equivalent linear codes: the support splitting algorithm, Information Theory, IEEE Transactions 46 (2000), 1193-1203.Search in Google Scholar

[52] SENDRIER, N. (ED.): Post-Quantum Cryptography, 3rd International Workshop- -PQCrypto ’10, Darmstadt, Germany, 2010 Lecture Notes in Comput. Sci., Vol. 6061, Springer, Berlin, 2010.Search in Google Scholar

[53] SENDRIER, N.: Decoding one out of many, in: Post-Quantum Cryptography, 4th Internat. Workshop-PQCrypto ’11, Taipei, Taiwan, 2011 (B.-Y. Yang, ed.), Lecture Notes in Comput. Sci., Vol. 7071, Springer, Berlin, 2011, pp. 51-67.Search in Google Scholar

[54] SHOUFAN, A.-STRENZKE, F.-MOLTER, H. G.-ST¨OTTINGER, M.: A timing attack against Patterson algorithm in the McEliece PKC, in: Proc. of the 12th Internat. Conf. on Information Security and Cryptology-ICISC ’09, Seoul, Korea, 2009 (D. Lee and S. Hong, eds.), Lecture Notes in Comput. Sci., Vol. 5984, Springer, Berlin, 2010, pp. 161-175 10.1007/978-3-642-14423-3_12Search in Google Scholar