Have a personal or library account? Click to login
Overview of the Mceliece Cryptosystem and its Security Cover

Overview of the Mceliece Cryptosystem and its Security

Tatra Mountains Mathematical Publications
Volume 60 (2014): Issue 1 (September 2014)
By: Marek Repka and  Pavol Zajac  
Open Access
|Mar 2015

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [28] GOPPA, V. D.: A new class of linear error correcting codes, Probl. Pered. Inform. 6 (1970), 24-30.
    Search in Google Scholar
  29. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [41] NIEDERREITER, H.: Knapsack-type cryptosystems and algebraic coding theory, Probl. Control Inf. Theory 15 (1986), 159-166.
    Search in Google Scholar
  42. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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
DOI: https://doi.org/10.2478/tmmp-2014-0025 | Journal eISSN: 1338-9750 | Journal ISSN: 12103195
Journal RSS Feed
Language: English
Page range: 57 - 83
Published on: Mar 11, 2015
Published by: Slovak Academy of Sciences, Mathematical Institute
In partnership with: Paradigm Publishing Services
Publication frequency: 3 issues per year
Keywords:
post-quantum cryptography,
McEliece cryptosystem,
side-channel attacks. Support by NATOs Public Diplomacy Division in the framework of “Science for Peace
Related subjects:
Mathematics,
General mathematics

© 2015 Marek Repka, Pavol Zajac, published by Slovak Academy of Sciences, Mathematical Institute
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Previous articleVolume 60 (2014): Issue 1 (September 2014)Next article