NewHopeKey Encapsulation Mechanism (KEM) has been presented at USENIX 2016 by Alkimet al.and was one of the lattice-based candidates to the post-quantum standardization initiated by the NIST. However, despite the relative simplicity of the protocol, the bound on the decapsulation failure probability resulting from the original analysis is not tight. In this work we refine this analysis to get a tight upper-bound on this probability which happens to be much lower than what was originally evaluated. As a consequence, we propose a set of alternative parameters, increasing the security and the compactness of the scheme. However using a smaller modulus prevent the use of a full NTT algorithm to perform multiplications of elements in dimension 512 or 1024. Nonetheless, similarly to previous works, we combine different multiplication algorithms and show that our new parameters are competitive on a constant time vectorized implementation. Our most compact parameters bring a speed-up of$17\%$(resp.$11\%$) in performance but allow to gain more than$19\%$over the bandwidth requirements and to increase the security of$10\%$(resp.$7\%$) in dimension 512 (resp. 1024).
NewHopeKey Encapsulation Mechanism (KEM) has been presented at USENIX 2016 by Alkimet al.and was one of the lattice-based candidates to the post-quantum standardization initiated by the NIST. However, despite the relative simplicity of the protocol, the bound on the decapsulation failure probability resulting from the original analysis is not tight. In this work we refine this analysis to get a tight upper-bound on this probability which happens to be much lower than what was originally evaluated. As a consequence, we propose a set of alternative parameters, increasing the security and the compactness of the scheme. However using a smaller modulus prevent the use of a full NTT algorithm to perform multiplications of elements in dimension 512 or 1024. Nonetheless, similarly to previous works, we combine different multiplication algorithms and show that our new parameters are competitive on a constant time vectorized implementation. Our most compact parameters bring a speed-up of17%(resp.11%) in performance but allow to gain more than19%over the bandwidth requirements and to increase the security of10%(resp.7%) in dimension 512 (resp. 1024).
Among many submissions to NIST post-quantum cryptography (PQC) project, NewHope is a promising key encapsulation mechanism (KEM) based on the Ring-Learning with errors (Ring-LWE) problem. Since NewHope is an indistinguishability (IND)-chosen ciphertext attack secure KEM by applying the Fujisaki-Okamoto transform to an IND-chosen plaintext attack secure public-key encryption, accurate calculation of decryption failure rate (DFR) is required to guarantee resilience against attacks that exploit decryption failures. However, the current upper bound (UB) on DFR of NewHope is rather loose because the compression noise, the effect of encoding/decoding of NewHope, and the approximation effect of centered binomial distribution are not fully considered. Furthermore, since NewHope is a Ring-LWE based cryptography, there is a problem of error dependency among error coefficients, which makes accurate DFR calculation difficult. In this paper, we derive much tighter UB on DFR than the current UB by using constraint relaxation and union bound. Especially, the above-mentioned factors are all considered in the derivation of new UB and the centered binomial distribution is not approximated. Since the error dependency is also considered, the new UB is much closer to the real DFR than the current UB. Furthermore, the new UB is parameterized by using Chernoff-Cramer bound to facilitate the calculation of new UB for the parameters of NewHope. Since the new UB is much lower than the DFR requirement of PQC, this DFR margin can be used to improve NewHope. As a result, the security level and bandwidth efficiency of NewHope are improved by 7.2 % and 5.9 %, respectively.
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.
SMAUG-T is a Module-LWE/LWR-based Key Encapsulation Mechanism (KEM) scheme, one of the Round 2 candidates in the Korean Post-Quantum Cryptography (KpqC) Standardization Competition. It partly follows the design of Kyber, the NIST’s PQC standard, while utilizing the sparse secret to achieve smaller sizes with better performance. Recently, Bernstein (KpqC-bulletin 2024) claimed that SMAUG-T contains sub-procedures that are not constant-time, which makes it vulnerable to an efficient key recovery attack. Additionally, Lee et al. (EPRINT 2024) presented an improved version of May’s Meet-LWE attack (Crypto 2021) on LWE using sparse secrets of fixed weights, which lowered the security of SMAUG-T level-5 parameter than the claimed security. In this paper, we first examine potential mitigation enabling SMAUG-T to be constant-time and assess their impact on performance. The performance decreases significantly compared to the original SMAUG-T, losing one of its strengths. Moreover, to make SMAUG-T secure against the attack of Lee et al., either sizes or decryption failure probability increases by a lot. To overcome this, we introduce new designs for SMAUG-T that allow us to bypass potential non-constant time vulnerabilities and attacks exploiting the sparse secret of fixed weights. These designs not only allow efficient timing-secure implementation but also reduce the sizes and the probability of decryption failures. Notably, the public key and ciphertext sizes are reduced by 10-20% for the level-5 parameters. When comparing constant-time implementations, the new SMAUG-T outperforms Kyber, the NIST’s PQC standard, by up to$1.6\times $for encapsulation and$1.4\times $for decapsulation.
A remarkable breakthrough in mathematics in recent years is the proof of the long-standing conjecture: sphere packing in theE8lattice is optimal in the sense of the best density for sphere packing inR8. In this work, we design a mechanism for asymmetric key consensus from noise (AKCN), referred to as AKCN-E8, for error correction and key consensus. As a direct application, we present a practical key encapsulation mechanism (KEM) from the ideal lattice based on the ring learning with errors (RLWE) problem. Compared with NewHope-KEM that was the second round candidate of the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) standardization, our AKCN-E8 KEM scheme overcomes some limitations and shortcomings of NewHope-KEM. Compared with some other dominating KEM schemes based on the variants of LWE, specifically Kyber and Saber, AKCN-E8 has a comparable performance but enjoys much flexible shared-key sizes. Specifically, the key encapsulated by AKCN-E8-512 (resp., 768, 1024) has the size of 256 (resp., 384, 512) bits. Flexible key size renders us stronger security against quantum attacks, more powerful and economic ability of key transportation, and better matches the demand in interactive protocols like TLS where parties need to negotiate the security parameters including the shared key length.
With the advent of quantum computers, traditional key exchange mechanisms are under threat, necessitating the development of new methods. Recently, Module-Lattice-Based Key Encapsulation Mechanism (ML-KEM) has been standardized as a quantum-safe key exchange method. Another emerging technique is Quantum Key Distribution (QKD) and its most famous protocol, BB84, which relies on the principles of quantum physics to exchange key information. Both techniques are considered secure against attacks by quantum computers, but their security is based on different principles. However, both key exchange types include a statistical component which, if an attacker were lucky, could allow circumventing these underlying hard problems. In this paper, we suggest that as a key exchange mechanism, BB84 should be run with security parameters comparable to those of ML-KEM, and analyze performance implications if this choice is taken. We illustrate the impact by estimating the number of raw bits required to generate a 256-bit symmetric key using BB84 and assessing the resulting performance implications. We further show how the BB84 finite-size security parameter can be chosen such that the post-processing failure probability is of the same order as the cumulative decapsulation-failure probability of ML-KEM. According to our results, the security parameter in BB84 should be at most 2−75.8 if statistical failure probability comparable to the ML-KEM decapsulation-failure target is desired. These findings offer general guidelines for BB84 parameter selection, with hybrid protocol design representing one potential application context.
Quantum computing and quantum computers have been discussed for almost three decades. However, they remain mainly in theory. Almost all big companies like Google, IBM, and Microsoft have put their effort to build the most scalable quantum computers in recent years. These computers can change the game in cryptography since the known hard problems such as integer factorization and discrete logarithms can be broken with a large-scale quantum computer. These computers would seriously jeopardize the confidentiality and integrity of all digital communications. The question of when large-scale quantum computers will be built is still an open question. There are some educated predictions that sufficiently large quantum computers will be built to break all public-key schemes currently in use within the next ten or so years. That is why the National Institute of Standards and Technology (NIST) has announced a standardization process in 2016 to prepare our information security systems to be able to resist in quantum computing. The first two rounds of this process have been completed, and there are seven on-going candidates and eight alternate candidates. Among these 15 schemes, seven of them are based on lattices. In this thesis, we study the efficient implementation of lattice-based schemes. We first propose an efficient and compact variant of NEWHOPE, one of the most efficient second-round candidates of the NIST post-quantum standardization project. The proposed algorithm NEWHOPE-COMPACT heavily uses recent advances on Number vii Theoretic Transform (NTT), so that transformation from one polynomial to another is easy. To make it possible, we changed the definition of a component in componentwise multiplication during polynomial multiplication and show that changing the security level only requires to change the size of the polynomial and the definition of a component. Then, we present various optimizations for lattice-based KEMs using the NTT on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, optimized small-degree polynomial multiplications, and more aggressive layer merging in the NTT, but also in the form of reduced stack usage. We test our optimizations in software implementations of KYBER, one of the round three candidates in the NIST post-quantum project, NEWHOPE, and NEWHOPE-COMPACT.