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.
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.
There are cryptographic systems that are secure against attacks by both classical and quantum computers. One of these systems is the NewHope key encapsulation mechanism (KEM) based on the Ring-learning with error problem (Ring-LWE problem). The Ring-LWE problem is presumed to be hard to solve even on a quantum computer. A KEM scheme allows sharing of a common key between two parts (Alice & Bob). This thesis presents original contributions to the security and analysis of key mismatch and information leakage attacks on NewHope KEM and some vulnerabilities on (small)-Ring-LWE problem (a variant of Ring-LWE problem). The first contribution contains some improvements on key mismatch attacks proposed by Bauer et al. and Qin et al. (Bauer et al., 2019; Qin et al., 2019). These key mismatch attacks retrieve Alices secret key. And, we propose two new methods named Fast Qin and Double Qin. The methods Fast Qin and Double Qin require around 240k and 34k oracle queries, respectively; instead of 840k queries of the Qin et al.s method. Moreover, these two new methods are adapted to retrieve Alices secret key on NewHope-512 (a variant of NewHope). The second contribution analyzes the information leakage of Bobs secret key on NewHope when it is reused. Our result corroborates that Bobs secret key must not be reused since with two communications to Bob, his secret key is leaked. In Ring-LWE problem, a polynomial a is selected randomly and a polynomial b is calculated as b = a.s+e where s is the secret polynomial (selected randomly) and the e is a noise polynomial. Our third contribution shows that in small-Ring-LWE, a variant where polynomials s and e are small, there are values of the public parameter a that leak a large percentage of the coefficients of the secret s. And, the last contribution shows that the secret s can be retrieved successfully if at least 50% of the random known coefficients of s and e are known.
This thesis is an in-depth introduction to NIST's post-quantum Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). We begin by introducing the problem at the core of ML-KEM, known as the Module Learning With Errors (MLWE) problem. In this problem, an adversary attempts to distinguish between samples selected from a specific distribution and samples from uniformly random samples. We also discuss the hardness of the MLWE problem, under the conjecture that certain lattice problems over modules are hard. ML-KEM utilizes a variant of the Fujisaki-Okamoto transformation, which employs a weakly secure Public-Key Encryption (PKE) scheme to construct a strongly secure key-encapsulation mechanism in the Random Oracle Model (ROM). We explain the working principle of the MLWE-based public-key encryption scheme and demonstrate how ML-KEM is constructed from it. Finally, we analyze the security of ML-KEM. We provide a tight security bound for IND-CCA security of ML-KEM in ROM, under the assumption that the underlying PKE is IND-CPA secure. Additionally, we present two security theorems in the Quantum Random Oracle Model (QROM). The first theorem establishes non-tightly IND-CCA security of ML-KEM in QROM if the MLWE problem is hard to solve. The second theorem assumes that the deterministic PKE is ciphertext-indistinguishable. Under this assumption, we derive a tighter bound for the IND-CCA security of ML-KEM in QROM.
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).
With the growing need for long-term secure communications in Internet-of-Things (IoT) and sensor-network environments, practical and robust post-quantum key-establishment mechanisms have become increasingly important. In this work, we revisit the ephemeral-only Ding key exchange (DKE) proposed at ACNS 2019, which is based on one-sample Ring Learning With Errors (Ring-LWE) with rounding, and the original analysis of which covers only passive security. Building on the DKE framework, we propose MoRo-KEM, a Module Learning With Errors (Module-LWE)-based key-encapsulation mechanism using rounding. First, we lift the construction from the Ring-LWE setting to the Module-LWE setting, retaining ring-level efficiency while enabling more flexible parameter choices and reducing reliance on rigid algebraic structure. Second, we replace discrete Gaussian sampling for secrets and errors with centered binomial sampling, thereby simplifying constant-time vectorized implementations while preserving the required noise behavior. Third, we extend the resulting key-exchange core to an IND-CPA-secure public-key encryption scheme and further obtain an IND-CCA-secure KEM via the Fujisaki-Okamoto transform. Finally, at security level I, MoRo-KEM achieves a decryption failure rate of 2-166, lower than the 2-139 reported for CRYSTALS-Kyber, thus improving robustness against decryption-failure attacks. These properties make the proposed design attractive for secure key establishment among sensor nodes, edge devices, and gateways operating under constrained computation, memory, and communication budgets. Overall, our construction provides a concrete path from ephemeral key exchange to a practical IND-CCA-secure KEM instantiated over Module-LWE.
In the field of post-quantum cryptography, lattice-based cryptography has received the most noticeable attention. Most lattice-based cryptographic schemes are constructed based on the polynomial ring Rq= Zq[x]/f (x), using a cyclotomic polynomial f (x). Until now, the most preferred cyclotomic polynomials have been xn+ 1, where n is a power of two, and xn+ · · · + x + 1, where n + 1 is a prime. The former results in the smallest decryption error size, but the choice of degree is limited. On the other hand, the latter gives rise to the largest decryption error size, but the choice of degree is very flexible. In this paper, we use a new polynomial ring Rq = Zq/f (x) with a cyclotomic trinomial f (x) = xn- xn/2+ 1 as an intermediate that combines the advantages of the other rings. Since the degree n is chosen freely as n = 2a3bfor positive integers a and b, the choice of the degree n is moderate. Furthermore, since the error propagation is small in the middle of polynomial multiplication in the new ring, if the middle part is truncated and used, the decryption error size can be reduced. Based on these observations, we propose a new, practical key encapsulation mechanism (KEM) that is constructed over a ring with a cyclotomic trinomial. The security of our KEM is based on the hardness of ring learning-with-rounding (LWR) problems. With appropriate parameterization for the current 128-bit security model, we show that our KEM obtains shorter secret keys and ciphertexts, especially compared to the previous Ring-LWR-based KEM, Round5, with no error correction code. We then implement our KEM and compare its performance with that of several KEMs that were presented in the second round of the NIST PQC conference.
Research on the security of lattice-based public-key encryption schemes against misuse attacks is an important part of the cryptographic assessment of the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) standardization process. In particular, many NIST-PQC cryptosystems follow the same meta-cryptosystem. At EUROCRYPT 2019, Ba˘etu et al. mounted a classical key recovery under plaintext checking attacks (KR-PCA) and a quantum key recovery under chosen ciphertext attacks (KR-CCA). They analyzed the security of the weak version of nine submissions to NIST. In this paper, we focus on learning with error (LWE)-based FrodoPKE, whose IND-CPA security is tightly related to the hardness of plain LWE problems. We first review the meta-cryptosystem and quantum algorithm for solving quantum LWE problems. Then, we consider the case where the noise follows a discrete Gaussian distribution and recompute the success probability for quantum LWE by using Hoeffding bound. Finally, we give a quantum key recovery algorithm based on LWE under CCA attack and analyze the security of Frodo. Compared with the existing work of Ba˘etu et al., our method reduces the number of queries from 22 to 1 with the same success probability.