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.
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.
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 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.
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.
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.
Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digitalsignature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of CRYSTALS - Cryptographic Suite for Algebraic Lattices - a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM), based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NEWHOPE KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme. We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki-Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than 128 bits of postquantum security.
The NTRU lattice is a promising candidate to construct practical cryptosystems, in particular key encapsulation mechanism (KEM), resistant to quantum computing attacks. Nevertheless, there are still some inherent obstacles to NTRU-based KEM schemes in having integrated performance, taking security, bandwidth, error probability, and computational efficiency \emph{as a whole}, that is as good as and even better than their \{R,M\}LWE-based counterparts. In this work, we solve this problem by presenting a new family of NTRU-based KEM schemes, referred to as CTRU and CNTR. By bridging low-dimensional lattice codes and high-dimensional NTRU-lattice-based cryptography with careful design and analysis, to the best of our knowledge CTRU and CNTR are the first NTRU-based KEM schemes with scalable ciphertext compression via only one \emph{single} ciphertext polynomial, and are the first that could outperform \{R,M\}LWE-based KEM schemes in integrated performance. For instance, compared to Kyber that is currently the only standardized KEM by NIST, on the recommended parameter set CNTR-768 has about 12% smaller ciphertext size while encapsulating 384-bit keys compared to the fixed 256-bit key size of Kyber, security strengthened by (8,7) bits for classical and quantum security respectively, and significantly lower error probability (2−230 of CNTR-768 vs. 2−164 of Kyber-768). In comparison with the state-of-the-art AVX2 implementation of Kyber-768, CNTR-768 is faster by 1.9X in KeyGen, 2.6X in Encaps, and 1.2X in Decaps, respectively. When compared to the NIST Round 3 finalist NTRU-HRSS, our CNTR-768 has about 15% smaller ciphertext size, and the security is strengthened by (55,49) bits for classical and quantum security respectively. As for the AVX2 implementation, CNTR-768 is faster than NTRU-HRSS by 19X in KeyGen, 2.3X in Encaps, and 1.6X in Decaps, respectively.