The article provides a comprehensive analysis of modern quantum-resistant cryptographic standards security based on lattice theory, such as DSTU 8961:2019 ("Skelya"), CRYSTALS-Kyber, and CRYSTALS-Dilithium. These standards are becoming increasingly popular for solving various practical tasks due to their resistance to attacks that can be implemented on quantum computers. As quantum computing gradually transitions from the theoretical to the practical realm, there is an urgent need for the development and improvement of security models capable of addressing these new challenges. This article focuses on applying the cryptanalysis model developed in previous works to specific cryptographic standards based on lattices. Special attention is given to refining security estimates by considering the algebraic structure of q-ary lattices, which form the foundation of the cryptographic problems underlying these standards. It was found that when considering the algebraic structure of q-ary lattices, security estimates differ significantly from those obtained using the GSA model. In particular, for the key encapsulation mechanisms of DSTU 8961:2019 and CRYSTALS-Kyber, the difference between the estimates in these two models can range from 20 to 30 bits of security, with the refined estimates indicating that existing attacks are less effective than previously thought. It was also revealed that for NIST Level 1 security, decoding attacks show better performance compared to embedding attacks, whereas for NIST Level 5 security, the effectiveness of decoding attacks decreases significantly, falling behind embedding attacks. Thus, the results highlight the importance of accounting for the algebraic structure of lattices in obtaining more accurate security assessments. This allows for a better understanding of potential threats and the optimization of existing lattice-based cryptographic transformations.
The article provides a comprehensive analysis of modern quantum-resistant cryptographic standards security based on lattice theory, such as DSTU 8961:2019 ("Skelya"), CRYSTALS-Kyber, and CRYSTALS-Dilithium. These standards are becoming increasingly popular for solving various practical tasks due to their resistance to attacks that can be implemented on quantum computers. As quantum computing gradually transitions from the theoretical to the practical realm, there is an urgent need for the development and improvement of security models capable of addressing these new challenges. This article focuses on applying the cryptanalysis model developed in previous works to specific cryptographic standards based on lattices. Special attention is given to refining security estimates by considering the algebraic structure of q-ary lattices, which form the foundation of the cryptographic problems underlying these standards. It was found that when considering the algebraic structure of q-ary lattices, security estimates differ significantly from those obtained using the GSA model. In particular, for the key encapsulation mechanisms of DSTU 8961:2019 and CRYSTALS-Kyber, the difference between the estimates in these two models can range from 20 to 30 bits of security, with the refined estimates indicating that existing attacks are less effective than previously thought. It was also revealed that for NIST Level 1 security, decoding attacks show better performance compared to embedding attacks, whereas for NIST Level 5 security, the effectiveness of decoding attacks decreases significantly, falling behind embedding attacks. Thus, the results highlight the importance of accounting for the algebraic structure of lattices in obtaining more accurate security assessments. This allows for a better understanding of potential threats and the optimization of existing lattice-based cryptographic transformations.
The study of key encapsulation mechanisms on structured lattices is one of the important directions in modern post-quantum cryptography, as many mechanisms are either already standardized (DSTU 8961:2019 "Skelya") or are promising candidates for standardization (CRYSTALS-Kyber). Estimating the complexity of lattice reduction for cryptographic schemes is an old problem. Asymptotic estimates differ greatly from experimental values, therefore, a number of heuristic methods were developed to solve practical problems. The coreSVP model is a standard means of assessing the security of cryptographic schemes on lattices. The purpose of the work is to analyze the encapsulation mechanisms of DSTU 8961:2019 "Skelya" and CRYSTALS-Kyber keys in the coreSVP model. The analysis was performed using two popular heuristics – GSA (Geometric Series Assumption) and the Chen-Nguyen simulator. The analysis showed that the Chen-Nguyen simulator gives slightly lower estimates than the GSA heuristic. As a result of the analysis, it was found that 8961:2019 The “Skelya” and CRYSTALS-Kyber in the coreSVP model for classical computers have slightly lower than declared security values, but for quantum computers the key encapsulation mechanisms provide the declared security levels. Note that during the analysis, the accuracy of the GSA heuristics and the Chen-Nguyen simulator were analyzed separately. Examples of parameters for which heuristics do not give sufficiently accurate results are given. The performed analysis does not take into account the algebraic structure of lattices used in 8961:2019 "Skelya" and CRYSTALS-Kyber. The inclusion of an algebraic structure in the analysis is a further direction of work. The use of simulators is a promising direction, however, more accurate simulators that take into account the structuring of LWE and NTRU arrays are needed.
The study of key encapsulation mechanisms on algebraic lattices is one of the important directions in modern post-quantum cryptography, since many mechanisms are already either standardized (ANSI X.9.98, DSTU 8961:2019 "Skelya") or are promising candidates for standardization (CRYSTALS-Kyber, FrodoKEM). The purpose of this work is to compare the security arguments of DSTU 8961:2019 "Skelya", CRYSTALS-Kyber, FrodoKEM key encapsulation mechanisms. The paper provides a comparison of theoretical evidence in the idealized random oracle (ROM) and quantum random oracle (QROM) models, as well as a comparison of specific values of security parameters in the core-SVP model, which is, in fact, a standard for lattice cryptography. Since all three key encapsulation mechanisms are based on different complex problems (NTRU, Module-LWE, LWE), a comparison of complex lattice theory problems and a comparison of their security arguments are additionally given. The strengths and weaknesses of the considered key encapsulation mechanisms are shown, and areas of research that require more detailed attention are highlighted.
In recent years, there has been a significant amount of research related to the development of quantum computers. If such a computer were to be built, it would be able to break existing public-key cryptosystems that are currently used for many purposes. This will seriously affect the privacy and integrity of digital communications, etc. That is why special attention is currently being paid to post-quantum cryptography, the main goal of which is the development of cryptographic systems that are protected from both quantum and classical attacks, and will also be able to interact with existing communication protocols and networks. In view of the significant importance of the practical application of directional encryption algorithms, at the international and state level, special attention was paid to the implementation of the proposed requirements for key encapsulation protocols. Key-establishment algorithms (KEA) form a common secret – the key for a symmetric encryption algorithm. The paper considers two KEA algorithms that use algebraic lattices: one of the finalists of the 3rd round Crystals-Kyber and the Skelya algorithm (DSTU 8961-2019). The Kyber algorithm first performs asymmetric encryption of a 32-byte message, and then generates a shared secret. The Skelya algorithm performs the same actions, but for asymmetric encryption, it uses messages of any length that do not exceed the maximum possible. That is why the last algorithm can be used not only as a KEA algorithm, but also as an asymmetric encryption algorithm. According to the NIST Security level, the Kyber algorithm provides cryptographic 1, 3, and 5 security levels, and the Rock algorithm provides cryptographic 3, 5, and 7 security levels. The cryptographic stability that is ensured for both algorithms is determined by a set of parameters. Thus, the purpose of this work is to review the details of the implementation of each of the mentioned algorithms, to compare the speed of the key generation, encapsulation and decapsulation algorithms for the Kyber and Skelya algorithms in terms of key data lengths, and the encapsulation result and computational complexity of both algorithms.
The advent of quantum computing will pose a substantial threat to the security of classical cryptographic methods, which could become vulnerable to quantum-based attacks. In response to this impending challenge, the field of post-quantum cryptography has emerged, aiming to develop algorithms that can withstand the computational power of quantum computers. This study addressed the pressing concern of classical cryptographic methods becoming vulnerable to quantum-based attacks due to the rise of quantum computing. The emergence of post-quantum cryptography has led to the development of new resistant algorithms. Our research focused on four quantum-resistant algorithms endorsed by America’s National Institute of Standards and Technology (NIST) in 2022: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+. This study evaluated the security, performance, and comparative attributes of the four algorithms, considering factors such as key size, encryption/decryption speed, and complexity. Comparative analyses against each other and existing quantum-resistant algorithms provided insights into the strengths and weaknesses of each program. This research explored potential applications and future directions in the realm of quantum-resistant cryptography. Our findings concluded that the NIST algorithms were substantially more effective and efficient compared to classical cryptographic algorithms. Ultimately, this work underscored the need to adapt cryptographic techniques in the face of advancing quantum computing capabilities, offering valuable insights for researchers and practitioners in the field. Implementing NIST-endorsed quantum-resistant algorithms substantially reduced the vulnerability of cryptographic systems to quantum-based attacks compared to classical cryptographic methods.
Modern cryptographic transformations require provable security against a relatively wide class of threats. Typically, such evidentiary security is achieved through formal analysis within the chosen security model. The development of quantum computers led to the emergence of new attack vectors to which classical cryptography was vulnerable. However, there are cryptographic systems that are considered resistant to quantum attacks and some of them are even standardized. The formal analysis of such systems has faced difficulties for a long time, which were associated with the impossibility of applying classical methods of proof to formal models that take into account quantum effects. However, in recent years, many new results have appeared that allow obtaining formal security proofs for quite complex cryptographic transformations, and most of the existing post-quantum asymmetric encryption and key encapsulation schemes currently have corresponding formal proofs within the quantum random oracle model, the most widespread security model for of post-quantum cryptography. DSTU 8961:2019 is the Ukrainian post-quantum standard for asymmetric encryption and key encapsulation. However, security proofs in the quantum random oracle model have not yet been published for it. As part of this work, security evidence was obtained for the design of the key encapsulation mechanism described in DSTU 8961:209. The obtained result is generalized for an arbitrary asymmetric encryption scheme, which may contain decryption errors and can be used to assess the security of not only DSTU 8961:2019, but also other similar asymmetric transformations.
Quantum-resistant cryptographic techniques refer to encryption and decryption methods crafted to resist potential attacks from quantum computers. Quantum computers, or QCs, possess the capacity to solve specific mathematical problems significantly faster than classical computers. Consequently, some widely employed cryptographic algorithms, like RSA and Elliptic Curve Cryptography (ECC), may become vulnerable to breaches by quantum computers. To safeguard sensitive data in the future, it becomes crucial to develop cryptographic algorithms that remain robust against potential attacks from quantum computers, thus ensuring the security of sensitive information. Quantum-resistant cryptographic algorithms are specifically engineered to provide this protection against quantum threats. One of the main challenges in developing quantum-resistant cryptographic algorithms is to ensure the security and efficiency for real-world applications. NIST has published Four Quantum-Resistant Cryptographic Algorithms - CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON and SPHINCS+. In this study, an analysis of these algorithms with various parameters, performance indicators and the capacity is performed, so that it gives an insight about the usage and effectiveness of the algorithms.