Modern variations of McEliece and Niederreiter cryptosystems
https://doi.org/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
Supporting agencies: 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.
About the Authors
V. V. Davydov
ITMO University
Russian Federation
Russian Federation
Vadim V. Davydov — Lecturer
197101, Saint Petersburg
V. V. Beliaev
ITMO University
Russian Federation
Russian Federation
Vladislav V. Beliaev — Laboratory Assistant
197101, Saint Petersburg
sc 57217737570
E. F. Kustov
ITMO University
Russian Federation
Russian Federation
Elizar F. Kustov – PhD Student
197101, Saint Petersburg
A. G. Leevik
ITMO University
Russian Federation
Russian Federation
Anton G. Leevik — Engineer
197101, Saint Petersburg
sc 57219714571
S. V. Bezzateev
ITMO University; Saint-Petersburg State University of Aerospace Instrumentation
Russian Federation
Russian Federation
Sergey V. Bezzateev — D. Sc., Full Professor, Associate Professor; Head of department
197101, Saint Petersburg
190000, Saint Petersburg
sc 6602425996
References
1. Shor P.W. Algorithms for quantum computation: discrete logarithms and factoring // Proc. of the 35th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 1994. P. 124–134. https://doi.org/10.1109/SFCS.1994.365700
2. McEliece R.J. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report 42–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. Mac Williams F.J., Sloane N.J.A. The theory of Error-Correcting Codes. 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. V. 6061. P. 81–94. https://doi.org/10.1007/978-3-642-12929-2_7
8. Sidelnikov V.M. A public-key cryptosystem based on binary ReedMuller codes // Discrete Mathematics and Applications. 1994. V. 4. N 3. P. 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. V. 4515. P. 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. P. 17–31.
11. Overbeck R. Structural attacks for public key cryptosystems based on Gabidulin codes // Journal of Cryptology. 2008. V. 21. N 2. P. 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. P. 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. P. 69–81.
14. Janwa H., Moreno O. McEliece public key cryptosystems using algebraic-geometric codes // Designs, Codes and Cryptography. 1996. V. 8. N 3. P. 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. V. 1976. P. 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. V. 49. N 12. P. 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. V. 5299. P. 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. Encryption scheme based on expanded reed-solomon codes // Advances in Mathematics of Communications. 2021. V. 15. N 2. P. 207–218. https://doi.org/10.3934/amc.2020053
20. Reed I.S., Solomon G. Polynomial codes over certain finite fields // Journal of the Society for Industrial and Applied Mathematics. 1960. V. 8. N 2. P. 300–304. https://doi.org/10.1137/0108018
21. 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. V. 12087. P. 41–49. https://doi.org/10.1007/978-3-030-54074-6_3
22. Berlekamp E., McEliece R., Van Tilborg H. On the inherent intractability of certain coding problems (corresp.) // IEEE Transactions on Information Theory. 1978. V. 24. N 3. P. 384–386. https://doi.org/10.1109/TIT.1978.1055873
23. 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. V. 3715. P. 64–83. https://doi.org/10.1007/11554868_6
24. Azouaoui A., Chana I., Belkasmi M. Efficient information set decoding based on genetic algorithms // International Journal of Communications, Network and System Sciences. 2012. V. 5. N 7. P. 423–429. https://doi.org/10.4236/ijcns.2012.57052
25. 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
26. 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. V. 9606. P. 144–161. https://doi.org/10.1007/978-3-319-29360-8_10
27. Lee Y., Cho J., Kim Y.-S., No J.-S. Cryptanalysis of the IvanovKabatiansky-Krouk-Rumenko cryptosystems // IEEE Communications Letters. 2020. V. 24. N 12. P. 2678–2681. https://doi.org/10.1109/LCOMM.2020.3019054
28. Patterson N. The algebraic decoding of Goppa codes // IEEE Transactions on Information Theory. 1975. V. 21. N 2. P. 203–207. https://doi.org/10.1109/TIT.1975.1055350
29. Berlekamp E.R. Non-binary BCH decoding. North Carolina State University. Dept. of Statistics, 1966.
Review
For citations:
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;22(2):324-331. (In Russ.) https://doi.org/10.17586/2226-1494-2022-22-2-324-331
Views:
11
Email this article 