On some cryptosystems based on algebraic codes

S. M. Ratseev ; O. I. Cherevatenko ; V. A. Chernyavskaya

Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, Tome 27 (2021) no. 1, pp. 62-73

Résumé

In 1978 McEliece built the first public key cryptosystem based on error-correcting codes. At the same time, effective attacks on the secret keys of this cryptosystem have not yet been found. The work describes the classical and modernized cryptosystems of McEliece and Niederreiter, also examples of their practical application based on Goppa codes using the Patterson algorithm. Also the algorithms of two-step authentication protocols with zero disclosure based on error-correcting codes are given.

Détail

Keywords: McEliece cryptosystem, error-correcting codes, code decoding.
Mots-clés : Goppa codes

Bibliographie

[1] McEliece R. J., “A Public-Key Cryptosystem Based On Algebraic Coding Theory”, DSN Progress Report, 42–44 (1978), 114–116

[2] Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process, Internal Report 8240, National Institute of Standards and Technology, January, 2019, 27 pp. | DOI

[3] Patterson N. J., “The algebraic decoding of Goppa codes”, IEEE Transactions on Information Theory, 21:2 (1975), 203–207 | DOI | MR | Zbl

[4] Ratseev S. M., “On decoding algorithms for Goppa codes”, Chelyabinsk Physical and Mathematical Journal, 5:3 (2020), 327–341 (In Russ.) | DOI | MR | Zbl

[5] Ratseev S. M., Cherevatenko O. I., “On a simple algorithm for decoding BCH codes, Reed-Solomon codes, and Goppa codes”, Vestnik SibGUTI, 2020, no. 3(51), 3–14 | MR

[6] Ratseev S. M., Cherevatenko O. I., “On decoding algorithms for generalized Reed-Solomon codes”, Systems and Means of Informatics, 30:4 (2020), 83–94 (In Russ.) | DOI

[7] Ratseev S. M., Cherevatenko O. I., “On decoding algorithms for generalized Reed-Solomon codes with errors and erasures”, Vestnik of Samara University. Natural Science Series, 26:3 (2020), 17–29 (In Russ.) | DOI | MR | Zbl

[8] Bhaskar Biswas, Nicolas Sendrier, “McEliece Cryptosystem Implementation: Theory and Practice”, Post-Quantum Cryptography, PQCrypto 2008, Lecture Notes in Computer Science, 5299, eds. Buchmann J., Ding J., Springer, Berlin–Heidelberg, 2008 | DOI | MR | Zbl

[9] Fitzpatrick P., Ryan J. A., “Counting irreducible Goppa codes”, Conference: Workshop on Coding and Cryptography (WCC) (Versaille, France, March 2003), 2003 https://www.researchgate.net/publication/276265397_Counting_irreducible_Goppa_codes | MR

[10] Niederreiter H., “Knapsack-type cryptosystems and algebraic coding theory”, Problems of Control and Information Theory, 15:2 (1986), 159–166 | MR | Zbl

[11] Bernstein Daniel J., Buchmann Johannes, Dahmen Erik (eds.), Post-Quantum Cryptography, Springer-Verlag, Berlin–Heidelberg, 2009 | DOI | MR

[12] Berlekamp E., McEliece R. J., Tilborg H. Van, “On the inherent intractability of certain coding”, IEEE Transactions on Information Theory, IT-24:3 (1978), 384–386 | DOI | MR | Zbl

[13] Sidelnikov V. M., “Cryptography and coding theory”, Materials of the conference «Moscow State University and Development of Cryptography in Russia», MGU, M., 2002, 22 pp. (In Russ.)

[14] Wang W., Szefer J., Niederhagen R., “FPGA-based key generator for the niederreiter cryptosystem using binary Goppa codes”, Cryptographic Hardware and Embedded Systems, CHES 2017, Lecture Notes in Computer Science, 10529, eds. Fischer W., Homma N., Springer, Cham, 2017, 253–274 | DOI | MR | Zbl

[15] Bernstein D., Chou T., Lange T., Maurich I., Misoczki R., Niederhagen R., Persichetti E., Peters C., Schwabe P., Sendrier N., Szefer J., Wang W., Classic McEliece: conservative code-based cryptography. Project documentation, 2019 (angl.) (accessed: 02.12.2020) https://classic.mceliece.org/nist/mceliece-20190331.pdf | MR

[16] ISO/IEC 9798–5:2009(E) «Information technology – Security techniques – Entity authentication – Part 5: Mechanisms using zero-knowledge technique», 2009 https://www.iso.org/standard/50456.html