A remarkable breakthrough in mathematics in recent years is the proof of the long-standing conjecture: sphere packing in the$E_{8}$lattice is optimal in the sense of the best density for sphere packing in$\mathbb {R}^{8}$. 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.
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.
In the last decade, there has been significant progress in the development of quantum computers, with massive investments by major tech companies. It is assumed that once large-scale quantum computers are built, many commonly used public key cryptosystems will no longer be secure. To prevent quantum attacks, researchers are already working on the design of post-quantum cryptographic protocols, and the US National Institute of Standards and Technology (NIST) is holding an international competition to select new cryptographic standards.Lattice-based cryptographic constructions are promising candidates because they offer strong theoretical security guarantees and can be implemented efficiently. One of the most widely used cryptographic primitives based on lattices is the Learning With Errors (LWE) problem introduced by Regev. Later works have proposed structured variants of LWE such as Ring-LWE and Module-LWE, which allow for a more compact representation.In this thesis, we consider two lattice-based NIST candidates for Key Encapsulation Mechanisms (KEMs) and propose new error correction and reconciliation techniques in order to improve their efficiency, their security, as well as their reliability.Unlike some previous works on error correction for lattice-based protocols, we provide rigorous error probability bounds.We first consider FrodoKEM, a lattice-based cryptosystem based on LWE, and introduce a modified error correction mechanism to improve its performance. Our encoder maps the secret key block-wise into a scaled version of the 8-dimensional Gosset lattice E_8. We propose three sets of parameters for our modified implementation. The first implementation outperforms FrodoKEM in terms of plausible security; the second allows to reduce the bandwidth by halving the modulus, and the third allows to increase key sizes.The second KEM we are considering is KyberKEM, which is based on Module-LWE. We propose a reconciliation technique using the lattice E_8, and show that our scheme can outperform KyberKEM in terms of security with comparable error probability and similar bandwidth requirements. We also investigate the use of higher dimensional lattices for reconciliation.
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.
The emergence of quantum computing threatens many classical cryptographic schemes, leading to the innovations in public-key cryptography for postquantum cryptography primitives and protocols that resist to quantum attacks. Lattice-based cryptography is considered to be one of the promising mathematical approaches to achieving security resistant to quantum attacks, which could be built on the learning with errors (LWE) problem and its variants. The fundamental building blocks of protocols for public-key encryption (PKE) and key encapsulation mechanism (KEM) submitted to the National Institute of Standards and Technology (NIST) based on LWE and its variants are called key consensus (KC) and asymmetric key consensus (AKC) by Jin et al. They are powerful tools for constructing PKE schemes. In this work, we further demonstrate the power of KC/AKC by proposing two special types of PKE schemes, namely, revocable attribute-based encryption (RABE). To be specific, on the basis of AKC and PKE/KEM protocols submitted to the NIST based on LWE and its variants, combined with full-rank difference, trapdoor on lattices, sampling algorithms, leftover hash lemma, and binary tree structure, we propose two directly revocable ciphertext-policy attribute-based encryption (DR-ABE) schemes from LWE, which support flexible threshold access policies on multivalued attributes, achieving user-level and attribute-level user revocation, respectively. Specifically, the construction of the ciphertext is derived from AKC, and the revocation list is defined and embedded into the ciphertext by the message sender to revoke a user in the user-level revocable scheme or revoke some attributes of a certain user in the attribute-level revocable scheme. We also discuss how to outsource decryption and reduce the workload for the end user. Our schemes proved to be secure in the standard model, assuming the hardness of the LWE problem. The two schemes imply the versatility of KC/AKC.
In this work, we abstract some key ingredients in previous LWE- and RLWE-based key exchange protocols, by introducing and formalizing the building tool, referred to as key consensus (KC) and its asymmetric variant AKC. KC and AKC allow two communicating parties to reach consensus from close values obtained by some secure information exchange. We then discover upper bounds on parameters for any KC and AKC. KC and AKC are fundamental to lattice based cryptography, in the sense that a list of cryptographic primitives based on LWR, LWE and RLWE (including key exchange, public-key encryption, and more) can be modularly constructed from them. As a conceptual contribution, this much simplifies the design and analysis of these cryptosystems in the future. We then design and analyze both general and highly practical KC and AKC schemes, which are referred to as OKCN and AKCN respectively for presentation simplicity. Based on KC and AKC, we present generic constructions of key exchange (KE) from LWR, LWE and RLWE. The generic construction allows versatile instantiations with our OKCN and AKCN schemes, for which we elaborate on evaluating and choosing the concrete parameters in order to achieve an optimally-balanced performance among security, computational cost, bandwidth efficiency, error rate, and operation simplicity.
Following the completion of the NIST post-quantum cryptography standardization, Kyber has been adopted as a key encapsulation mechanism (KEM) for quantum-resistant communication. Although lattice-based KEMs provide strong security and efficiency, most existing designs restrict the cyclotomic ring dimension to powers of two, which limits parameter flexibility for heterogeneous and resource-constrained Internet of Things (IoT) devices. In this paper, we propose Fyber, a post-quantum KEM based on the Module Learning With Errors (M-LWE) problem over a module ring defined by the cyclotomic polynomial f(x)=xn−xn/2+1, where n is a product of powers of 2 and 3. This construction enables mixed-radix parameter selection and allows finer-grained trade-offs between security and efficiency. To further improve performance on constrained platforms, we introduce an efficient non-Gaussian sampling method. The proposed KEM supports flexible security-level stratification for IoT applications, achieving reduced public key and ciphertext sizes for selected parameter sets at the cost of moderately increased computational overhead compared to Kyber, and fills intermediate security gaps between existing standardized parameter sets.
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.