Post-quantum algorithm of Classic McEliece key encapsulation

Abstract

A comprehensive analysis of a candidate-finalist of the International Post-quantum Cryptography Competition NIST PQC, namely, the Classic McEliece algorithm, the key encapsulation algorithm based on code cryptosystems, is carried out. The aim of this work is a primary study of the basic characteristics of the Classic McEliece algorithm, such as the mathematical model, the expected cryptographic strength and quantitative assessment of the resources.
The paper gives the analysis of the mathematical model of the Classic McEliece algorithm, description of the main functions and transformations, comparison of the primary model of the algorithm proposed by Robert McEliece in 1978 with the considered algorithm, analysis of the modifications made by the authors of Classic McEliece. It also provides recommendations for further areas of research and refinement of the algorithm. As a primary assessment of cryptographic security, an analysis of compliance with modern requirements for post-quantum cryptosystems is carried out, namely, ensuring the property of indistinguishability for attacks based on selected plaintext, indistinguishability for non-adaptive and adaptive attacks based on selected cipher text.
The paper analyzes the memory costs for storing system parameters, evaluating the impact of their size on the system performance. The characteristics of the Classic McEliece algorithm are compared with similar algorithms based on the algebraic codes presented as alternatives at the NIST PQC Competition, namely, the BIKE and HQC algorithms. The performance evaluation is carried out for three basic functions of the algorithm: keys generation, encapsulation and de-encapsulation.