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.
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.
In recent years, there has been significant progress in the creation of quantum computers. If scalable quantum computers are implemented in the near future, this will jeopardize the security of the most widely used public key cryptosystems. The most vulnerable are public-key schemes based on factorization, discrete logarithms and elliptic curve cryptography. Currently, the main task is to develop, evaluate, study and standardize asymmetric crypto transformations at the international level, including mechanisms of key encapsulation and directional encryption, resistant to attacks by violators of the post-quantum period. An important feature of the transition and post-quantum period is the usage of new mathematical methods to opposite quantum crypto analysis. The paper considers the main attacks on the mechanisms of key encapsulation and directional encryption, as well as system-wide parameters of the DSTU 8961: 2019 standard, which affect the resistance to attacks and the complexity of transformations. Methods for generating system-wide parameters of 5 and 7 levels of stability – 512 bits of classical and 256 bits of quantum security, as well as the protection of the algorithm from attacks by third-party channels are considered. The dependence of encryption and decryption time on the level of stability is analyzed. The results of calculations of system-wide parameters for stability levels 256/128, 384/192 and 512/256 are presented, as well as recommendations for the selection of system-wide parameters depending on the environment and computing capabilities. Sets of parameters selected and recommended for use in the DSTU 8961: 2019 standard are given. Conclusions are drawn about the possibility of applying the DSTU 8961 standard in the post-quantum period.
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.
Recent developments in quantum computers pose an imminent threat to cryptography since many widely used cryptographic schemes will no longer be secure. This worrisome scenario motivated a growing interest in the field of post-quantum cryptography, which aims to design cryptosystems that are postquantum secure, i.e. secure against quantum-capable adversaries. While finding post-quantum computational hardness assumptions is pivotal to achieve this goal, an issue that is often overlooked is provable security. In fact, to prove that the post-quantum computational hardness necessarily implies post-quantum security of the derived cryptosystem, the reduction argument that establishes this implication also needs to be post-quantum. As such, many new methods have been devised in the last few years to handle this adaptation to the quantum setting. In particular, the quantum analogue of the Random Oracle Model has garnered special interest, as it is the foundation of many cryptographic schemes, from public-key encryption to digital signatures. It is also very problematic and usually the main culprit of the failure of security proofs when transitioning to the quantum setting. This work offers a comprehensive exposition on the most influential techniques developed in the last decade to enable or facilitate the construction of security proofs in the Quantum Random Oracle Model (QROM). Each presented technique offers an unique purpose and a solution to a problem provoked by the QROM, and, as such, as a whole, this works allows for an understanding of the most common strategies to construct these type of security proofs. This is accomplished by presenting and analyzing the security proof of three cryptographic schemes set in this model, which underlines the central role these techniques take in provable quantum security.
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 this paper, the essence is considered and security models of asymmetric post-quantum cryptographic primitives of different types are investigated. The basis taken security models that are recommended by NIST USA in the requirements of the PQC competition for candidates for post-quantum cryptographic primitives. Such algorithms include asymmetric cryptographic transformations such as asymmetric encryption, digital signature, and key encapsulation mechanism. The following security models are recommended, which are related to: the asymmetric encryption — IND-CCA2 (IND-CPA, IND-CCA); the digital signature — EUF-CMA (and its variations); the key encapsulation mechanisms — СK-model. In this paper, the basic essence of such security models is considered. The use of security models in research of cryptographic primitives is relatively new. A generalization of each of these models and a definition of the necessity and conditions, and the consequences of their application are required. Such models take into account the application environment in which an unauthenticated-links adversarial model and authenticated-links adversarial model can operate. The paper considers the concept of indistinguishability and security model of post-quantum asymmetric ciphers on its basis. The property of indistinguishability under chosen plaintext attack is determined. The concept of semantic security is considered. The types of most common attacks based on indistinguishability are given. Existing versions of the EUF-CMA security model — SUF-CMA, etc. are considered. Definitions of «forward security, forward secrecy» and «perfect forward secrecy (PFS)» are given. In addition, the paper considers the peculiarities of the application regarding to perspective asymmetric transformations of the «game theory». The definition of concept «game theory» is given
Abstract It is viewed as revolutionary technology, offering incredible potential in terms of computing power within different scientific and industrial sectors. Quantum computers provide remarkable computing power; however, they also present significant security risks to existing public-key cryptography systems used to secure digital communication, online banking systems, government, medical applications, cloud computing systems, and IoT systems. Security of commonly used encryption schemes like RSA, DH, and ECC depends on mathematical problems that are impossible for classical computers to solve but can be easily resolved with the help of powerful enough quantum computers by using Shor’s algorithm. Furthermore, Grover’s algorithm makes exhaustive search attacks much faster, thus effectively lowering the security level of symmetric encryption schemes since it provides the speed-up for brute-force attacks. Post-Quantum Cryptography (PQC) turned out to be an effective and scalable method to protect digital data from attacks using quantum computing. In contrast to quantum cryptography, which requires a special quantum communication channel, PQC uses classical cryptographic algorithms that cannot be broken down by either classical or quantum computer due to certain mathematical problems. This research paper offers an extensive exploration of post-quantum cryptography through the analysis of the development of quantum computing, weaknesses of current cryptographic techniques, and mathematics behind quantum-resistant algorithms. Moreover, this paper explores the major classes of PQC techniques such as lattice-based, code-based, hash-based, multivariate, and isogeny-based cryptography and provides details about their security and application. Moreover, the report gives an overview of the NIST Post-Quantum Cryptography Standardization Project and analyzes recent standardizations of quantum-proof algorithms to be utilized in future digital infrastructures. Keywords: Post-Quantum Encryption, Quantum Security, Quantum-Proof Public-Key Cryptography, Lattice-Based Security Protocols, ML-KEM Key Encapsulation Mechanism, ML-DSA Digital Signature Algorithm, NIST Post-Quantum Cryptography, Contemporary Cybersecurity, Secure Communications, Cryptographic Algorithms.