Análise de variantes do criptossistema McEliece e da versão candidata a padrão de encriptação baseada em códigos
Resumo
Este trabalho discorre sobre a segurança de algumas variantes do criptossistema McEliece. Para tanto, são analisados trabalhos que, a partir de mudanças estruturais e/ou paramétricas, buscaram torná-lo mais eficiente. Observa-se que, dentre as variantes avaliadas, as baseadas em Código Goppa mantiveram o mesmo nível de segurança e alcançaram as melhorias propostas, em parte com a mudança de parâmetros e otimizações através de list decoding; as demais, baseadas em estruturas menos conservadoras, foram quebradas, porém inspiram outras formas de otimização.
Palavras-chave:
McEliece, Segurança, Criptografia de chave pública
Referências
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.
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.
Publicado
04/10/2021
Como Citar
MARTINEZ, Guilherme G.; GOYA, Denise Hideko.
Análise de variantes do criptossistema McEliece e da versão candidata a padrão de encriptação baseada em códigos. In: WORKSHOP DE TRABALHOS DE INICIAÇÃO CIENTÍFICA E DE GRADUAÇÃO - SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 21. , 2021, Evento Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 124-137.
DOI: https://doi.org/10.5753/sbseg_estendido.2021.17347.
