Analysis of variants of the McEliece cryptosystem and the code-based encryption standard candidate version

• Guilherme G. Martinez UFABC
• Denise Hideko Goya UFABC

DOI: https://doi.org/10.5753/sbseg_estendido.2021.17347

Abstract

This work discusses the security of some variants of the McEliece cryptosystem. Therefore, works that, from structural and/or parametric changes, sought to make it more efficient are analyzed. It is observed that, among the variants evaluated, those based on Goppa Code maintained the same level of security and achieved the proposed improvements, in part with the change of parameters and optimizations through list decoding; the others, based on less conservative structures, were broken, but inspire other forms of optimization.

Keywords: McEliece, Security, Public-key cryptography

References

Albrecht, M. R., Bernstein, D. J., Chou, T., Cid, C., Gilcher, J., and Lange, T. (2020). Classic McEliece. https://classic.mceliece.org/. Submissão NIST, Acesso em: 21/06/2021.

Aragon, N., Barreto, P., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Gaborit, P., Gueron, S., Guneysu, T., Melchor, C. A., et al. (2017). BIKE: bit ipping key encapsulation. https://bikesuite.org/. Submissão NIST, Acesso em: 21/06/2021.

Baldi, M., Bianchi, M., Chiaraluce, F., Rosenthal, J., and Schipani, D. (2016). Enhanced public key security for the mceliece cryptosystem. Journal of Cryptology, 29(1):1–27.

Baldi, M. and Chiaraluce, F. (2007). Cryptanalysis of a new instance of mceliece cryptosystem based on qc-ldpc codes. In 2007 IEEE International Symposium on Information Theory, pages 2591–2595. IEEE.

Bardet, M., Chaulet, J., Dragoi, V., Otmani, A., and Tillich, J.-P. (2016). Cryptanalysis of the mceliece public key cryptosystem based on polar codes. In Post-Quantum Cryptography, pages 118–143. Springer.

Barreto, P., Biasi, F. P., Dahab, R., César, J., Pereira, G., and Ricardini, J. E. (2013). Introdução à criptograa pós-quântica. Minicursos do XIII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, SBSeg.

Berger, T. P., Cayrel, P.-L., Gaborit, P., and Otmani, A. (2009). Reducing key length of the mceliece cryptosystem. In International Conference on Cryptology in Africa, pages 77–97. Springer.

Bernstein, D. J., Lange, T., and Peters, C. (2008). Attacking and defending the mceliece cryptosystem. In International Workshop on Post-Quantum Cryptography, pages 31– 46. Springer.

Bernstein, D. J., Lange, T., and Peters, C. (2010). Wild mceliece. In International Workshop on Selected Areas in Cryptography, pages 143–158. Springer.

Blahut, R. E. (2003). Algebraic codes for data transmission. Cambridge university press.

Both, L. and May, A. (2018). Decoding linear codes with high error rate and its impact for lpn security. In International Conference on Post-Quantum Cryptography, pages 25–46. Springer.

Buchmann, J. (2013). Introduction to cryptography. Springer Science & Business Media.

Canteaut, A. and Sendrier, N. (1998). Cryptanalysis of the original mceliece cryptosystem. In International Conference on the Theory and Application of Cryptology and Information Security, pages 187–199. Springer.

Dragoi, V. and Kalachi, H. T. (2017). Cryptanalysis of a public key encryption scheme based on qc-ldpc and qc-mdpc codes. IEEE Communications letters, 22(2):264–267.

Engelbert, D., Overbeck, R., and Schmidt, A. (2007). A summary of mceliece-type cryptosystems and their security:. Journal of Mathematical Cryptology, 1(2):151–199.

Faugere, J.-C., Otmani, A., Perret, L., and Tillich, J.-P. (2010). Algebraic cryptanalysis of mceliece variants with compact keys. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 279–298. Springer.

Goldwasser, S. and Bellare, M. (1996). Lecture notes on cryptography. Summer course “Cryptography and computer security” at MIT, 1999:1999.

Goppa, V. D. (1970). A new class of linear correcting codes. Problemy Peredachi Informatsii, 6(3):24–30.

Hill, R. (1986). A rst course in coding theory. Oxford University Press.

Kurose, J. F., Ross, K. W., and Zucchi, W. L. (2007). Redes de Computadores e a Internet: uma abordagem top-down. Pearson Addison Wesley.

Li, Y. X., Deng, R. H., and Wang, X. M. (1994). On the equivalence of mceliece’s and niederreiter’s public-key cryptosystems. IEEE Transactions on Information Theory, 40(1):271–273.

McEliece, R. J. (1978). A public-key cryptosystem based on algebraic. Coding Thv, 4244:114–116.

Minder, L. and Shokrollahi, A. (2007). Cryptanalysis of the sidelnikov cryptosystem. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 347–360. Springer.

Monico, C., Rosenthal, J., and Shokrollahi, A. (2000). Using low density parity check codes in the mceliece cryptosystem. In 2000 IEEE International Symposium on Information Theory (Cat. No. 00CH37060), page 215. IEEE.

Moufek, H., Guenda, K., and Gulliver, T. A. (2016). A new variant of the mceliece cryptosystem based on qc-ldpc and qc-mdpc codes. IEEE Communications Letters, 21(4):714–717.

Niederreiter, H. (1986). Knapsack-type cryptosystems and algebraic coding theory. Prob. Control and Inf. Theory, 15(2):159–166.

NIST (2017). for Proposals. Post-Quantum Cryptography PQC Call [link]. Acesso em: 21/06/2021.

Otmani, A., Tillich, J.-P., and Dallot, L. (2008). Cryptanalysis of mceliece cryptosystem based on quasi-cyclic ldpc codes. In Proceedings of First International Conference on Symbolic Computation and Cryptography, pages 69–81. LMIB Beihang University.

Otmani, A., Tillich, J.-P., and Dallot, L. (2010). Cryptanalysis of two mceliece cryptosystems based on quasi-cyclic codes. Mathematics in Computer Science, 3(2):129–140.

Overbeck, R. and Sendrier, N. (2009). Code-based cryptography. In Post-quantum cryptography, pages 95–145. Springer.

Repka, M. and Cayrel, P.-L. (2014). Cryptography based on error correcting codes: A survey. In Multidisciplinary Perspectives in Cryptology and Information Security, pages 133–156. IGI Global.

Sendrier, N. (2000). Finding the permutation between equivalent linear codes: The support splitting algorithm. IEEE Transactions on Information Theory, 46(4):1193–1203.

Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332.

Shrestha, S. R. and Kim, Y.-S. (2014). New mceliece cryptosystem based on polar codes as a candidate for post-quantum cryptography. In 2014 14th International Symposium on Communications and Information Technologies (ISCIT), pages 368–372. IEEE.

Van Leeuwen, J. and Leeuwen, J. (1990). Handbook of theoretical computer science: Algorithms and complexity, volume 1. Elsevier.

Yan, S. Y. (2009). Primality testing and integer factorization in public-key cryptography. Springer.

Zajac, M. R. (2014). Overview of the mceliece cryptosystem and its security. Tatra Mt. Math. Publ, 60:57–83.

Zhang, Q., Li, Z., and Song, C. (2011). The improvement of digital signature algorithm based on elliptic curve cryptography. In 2011 2nd International Conference on Articial Intelligence, Management Science and Electronic Commerce (AIMSEC), pages 1689–1691. IEEE.