Overview of the Mceliece Cryptosystem and its Security

Marek Repka; Pavol Zajac

doi:10.2478/tmmp-2014-0025

Abstract

McEliece cryptosystem (MECS) is one of the oldest public key cryptosystems, and the oldest PKC that is conjectured to be post-quantum secure. In this paper we survey the current state of the implementation issues and security of MECS, and its variants. In the first part we focus on general decoding problem, structural attacks, and the selection of parameters in general. We summarize the details of MECS based on irreducible binary Goppa codes, and review some of the implementation challenges for this system. Furthermore, we survey various proposals that use alternative codes for MECS, and point out some attacks on modified systems. Finally, we review notable existing implementations on low-resource platforms, and conclude with the topic of side channels in the implementations of MECS

References

[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-9
Search 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.1055873
Search 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_16
Search 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_2
Search 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.009
Search 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.2272036
Search 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.1057683
Search 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_25
Search 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.21270
Search 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.6620590
Search 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-2
Search 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-9
Search 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-8
Search 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_4
Search 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.1055350
Search 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.ch005
Search 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_12
Search in Google Scholar

Overview of the Mceliece Cryptosystem and its Security

Abstract

Paradigm

My account