ENG
РУС
Search
Menu
About the Edition
Open Access Statement
Editorial Board
Editorial Policy
Editorial Ethics
Rules for peer-review
Rules for presentation of papers
Forms of Submitted Documents
Recommendations for the Design of References to Our Journal
Editorial Staff
Information for Subscribers
Summaries of the Issue
List of Authors
Issues
Publishers license agreement
Procedure of work with personal data
Publications
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.
Partners













































doi: 10.17586/2226-1494-2022-22-2-324-331

Modern variations of McEliece and Niederreiter cryptosystems

V. V. Davydov, V. V. Beliaev, E. F. Kustov, A. G. Leevik, S. V. Bezzateev


Read the full article  ';
Article in Russian

For citation:
Davydov V.V., Beliaev V.V., Kustov E.F., Leevik A.G., Bezzateev S.V. Modern variations of McEliece and Niederreiter cryptosystems. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2022, vol. 22, no. 2, pp. 324–331 (in Russian). doi: 10.17586/2226-1494-2022-22-2-324-331


Abstract
Classical cryptosystems proposed by Robert McEliece (1978) and Harold Niederreiter (1986) and their modern variations are studied. A detailed review of five code-based public key cryptosystems has been presented. It is shown that some of the modern interpretations of the classical McEliece and Niederreiter cryptosystems have significant issues. In particular, it has been established that the XGRS cryptosystem based on extended Reed-Solomon codes does not provide the declared level of security against the information set decoding attack, and also has a number of inaccuracies. It is shown that the time of key generation and decryption in modern cryptosystems is quite large, and the public and private keys take up a large amount of memory. The inaccuracies of the considered schemes revealed in this work can be used to improve and adjust the systems, as well as to build a more accurate assessment of their security level and efficiency. The presented cryptosystems can be considered as standards for post-quantum cryptography and can be used to protect data after development of powerful quantum computers.

Keywords: post-quantum cryptography, McEliece cryptosystem, Niederreiter cryptosystem, binary Goppa codes, generalized Reed-Solomon codes

Acknowledgements. The work is made as a part of research work no. 620164 at ITMO University. This project has received financial support from the Priority 2030 Federal Academic Leadership Program. We thank Jean-Michelle Dakuo for his help in programming implementation.

References
  1. Shor P.W. Algorithms for quantum computation: discrete logarithms and factoring. Proc.of the35th IEEE Annual Symposium on Foundations of Computer Science(FOCS),1994, pp. 124–134.https://doi.org/10.1109/SFCS.1994.365700
  2. McElieceR.J. Apublic-key cryptosystem base donalgebraic codingtheory. DSNProgressReport42-44, 1978, pp. 114–116.
  3. Goppa V.D. A Rational Representation of Codes and (L,g)-Codes. Problems Information Transmission, 1971, vol. 7, no.3. pp. 223–229.
  4. Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory, 1986, vol. 15, no. 2, pp. 159–166.
  5. MacWilliamsF.J., SloaneN.J.A. ThetheoryofError-CorrectingCodes. Amsterdam, 1977.
  6. Sidel'nikov V.M., Shestakov S.O. On an encoding system constructed on the basis of generalized Reed–Solomon codes. Discrete Mathematics and Applications, 1992, vol. 2, no. 4, pp. 439–444.
  7. Peters C. Information-set decoding for linear codes over Fq.Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),2010, vol. 6061, pp. 81–94. https://doi.org/10.1007/978-3-642-12929-2_7
  8. Sidelnikov V.M. A public-key cryptosystem based on binary Reed-Muller codes. Discrete Mathematics and Applications, 1994, vol. 4, no. 3, pp. 191–207. https://doi.org/10.1515/dma.1994.4.3.191
  9. Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2007,vol. 4515, pp. 347–360. https://doi.org/10.1007/978-3-540-72540-4_20
  10. Gabidulin E.M. Public-key cryptosystems based on linear codes.Report 95-30. Delft University of Technology, Faculty of Technical Mathematics and Informatics, 1995, pp. 17–31.
  11. Overbeck R. Structural attacks for public key cryptosystems based on Gabidulin codes.Journal of Cryptology, 2008, vol. 21, no. 2, pp. 280–301.https://doi.org/10.1007/s00145-007-9003-9
  12. Baldi M., Chiaraluce F. Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes. Proc. of the IEEE International Symposium on Information Theory (ISIT), 2007, pp. 2591–2595. https://doi.org/10.1109/ISIT.2007.4557609
  13. Otmani A., Tillich J.P., Dallot L. Cryptanalysis of McEliece cryptosystem based on quasi-cyclic LDPC codes. Proc. of the First International Conference on Symbolic Computation and Cryptography. LMIB Beihang University, 2008, pp. 69–81.
  14. Janwa H., Moreno O. McEliece public key cryptosystems using algebraic-geometric codes. Designs, Codes and Cryptography, 1996, vol. 8, no. 3, pp. 293–307. https://doi.org/10.1023/A:1027351723034
  15. Faure C., Minder L. Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes. Proc. of the 11th International Workshop on Algebraic and Combinatorial Coding Theory, 2008, P. 99–107.
  16. Loidreau P. Strengthening McEliece cryptosystem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),2000, vol. 1976, pp. 585–598. https://doi.org/10.1007/3-540-44448-3_45
  17. Kobara K., Imai H. On the one-wayness against chosen-plaintext attacks of the Loidreau's modified McEliece PKC.IEEE Transactions on Information Theory, 2003, vol. 49, no. 12, pp. 3160–3168.https://doi.org/10.1109/TIT.2003.820016
  18. Bernstein D.J., Lange T., Peters C. Attacking and defending the McEliece cryptosystem.Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),2008, vol. 5299, pp. 31–46.https://doi.org/10.1007/978-3-540-88403-3_3
  19. Bernstein D.J. et al. Classic McEliece: conservative code-based cryptography. NIST, 2017.
  20. Khathuria K., Rosenthal J., Weger V. Encryptionscheme based on expanded reed-solomon codes.Advances in Mathematics of Communications, 2021, vol. 15, no. 2, pp. 207–218.https://doi.org/10.3934/amc.2020053
  21. Reed I.S., Solomon G. Polynomial codes over certain finite fields.Journal of the Society for Industrial and Applied Mathematics, 1960, vol. 8, no. 2, pp. 300–304.https://doi.org/10.1137/0108018
  22. Ivanov F., Kabatiansky G., Krouk E., Rumenko N.A new code-based cryptosystem.Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),2020, vol. 12087, pp. 41–49.https://doi.org/10.1007/978-3-030-54074-6_3
  23. Berlekamp E., McEliece R., Van Tilborg H. On the inherent intractability of certain coding problems (corresp.).IEEE Transactions on Information Theory, 1978, vol. 24, no. 3, pp. 384–386.https://doi.org/10.1109/TIT.1978.1055873
  24. Augot D., Finiasz M., Sendrier N. A family of fast syndrome based cryptographic hash functions. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),2005, vol. 3715, pp. 64–83.https://doi.org/10.1007/11554868_6
  25. Azouaoui A., Chana I., Belkasmi M. Efficient information set decoding based on genetic algorithms. International Journal of Communications, Network and System Sciences,2012, vol. 5, no. 7,pp. 423–429. https://doi.org/10.4236/ijcns.2012.57052
  26. Gauthier V., Otmani A., Tillich J.P. A Distinguisher-based attack on a variant of McEliece's cryptosystem based on Reed-Solomon codes.arXiv.org, 2012, arXiv:1204.6459. https://doi.org/10.48550/arXiv.1204.6459
  27. Torres R.C., Sendrier N. Analysis of information set decoding for a sub-linear error weight.Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),2016, vol. 9606, pp. 144–161.https://doi.org/10.1007/978-3-319-29360-8_10
  28. Lee Y., Cho J., Kim Y.-S., No J.-S.Cryptanalysis of the Ivanov-Kabatiansky-Krouk-Rumenko cryptosystems.IEEE Communications Letters, 2020, vol. 24, no. 12, pp. 2678–2681.https://doi.org/10.1109/LCOMM.2020.3019054
  29. Patterson N. The algebraic decoding of Goppa codes.IEEE Transactions on Information Theory, 1975, vol. 21, no. 2, pp. 203–207.https://doi.org/10.1109/TIT.1975.1055350
  30. Berlekamp E.R. Non-binary BCH decoding. North Carolina State University. Dept. of Statistics, 1966.


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2024 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.

Яндекс.Метрика