In order to resist the security risks caused by quantum computing, post-quantum cryptography (PQC) has been a research focus. Constructing a key encapsulation mechanism (KEM) based on lattices is one of the promising PQC routines. The algebraically structured learning with errors (LWE) problem over power-of-two cyclotomics has been one of the most widely used hardness assumptions for lattice-based cryptographic schemes. However, power-of-two cyclotomic rings may be exploited in the inflexibility of selecting parameters. Recently, trinomial cyclotomic rings of the form Zq[x]/(xn−xn/2+1), where n=2k3l, k≥1,l≥0, have received widespread attention due to their flexible parameter selection. In this paper, we propose Tyber, a variant scheme of the NIST-standardized KEM candidate Kyber over trinomial cyclotomic rings. We provide three parameter sets, aiming at the quantum security of 128, 192, and 256 bits (actually achieving 129, 197, and 276 bits) with matching and negligible error probabilities. When compared to Kyber, our Tyber exhibits stronger quantum security, by 22, 31, and 44 bits, than Kyber for three security levels.
In order to resist the security risks caused by quantum computing, post-quantum cryptography (PQC) has been a research focus. Constructing a key encapsulation mechanism (KEM) based on lattices is one of the promising PQC routines. The algebraically structured learning with errors (LWE) problem over power-of-two cyclotomics has been one of the most widely used hardness assumptions for lattice-based cryptographic schemes. However, power-of-two cyclotomic rings may be exploited in the inflexibility of selecting parameters. Recently, trinomial cyclotomic rings of the form Zq[x]/(xn−xn/2+1), where n=2k3l, k≥1,l≥0, have received widespread attention due to their flexible parameter selection. In this paper, we propose Tyber, a variant scheme of the NIST-standardized KEM candidate Kyber over trinomial cyclotomic rings. We provide three parameter sets, aiming at the quantum security of 128, 192, and 256 bits (actually achieving 129, 197, and 276 bits) with matching and negligible error probabilities. When compared to Kyber, our Tyber exhibits stronger quantum security, by 22, 31, and 44 bits, than Kyber for three security levels.
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.
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.
The ongoing transition to Post-Quantum Cryptography (PQC) has highlighted the need for cryptographic schemes that offer high security, strong performance, and fine-grained parameter selection. In lattice-based cryptography, particularly for the popular module variants of learning with errors (Module-LWE) and learning with rounding (Module-LWR) schemes based on power-of-two cyclotomics, existing constructions often force parameter choices that either overshoot or undershoot desired security levels due to structural constraints. In this work, we introduce a new class of techniques that are the advantages of both worlds: structured Module-LWE (or LWR) embeds more algebraic structure than a module such that it significantly improves performance, yet less structure than a power-of-two cyclotomic ring such that it still enables more flexible and efficient parameter selection. We present two concrete instances: a construction based on a radical extension of a two-power cyclotomic field denoted radical Ring-LWE (RR-LWE) or Ring-LWR (RR-LWR), and a cyclotomic block-ring module lattice approach (BRM-LWE or BRM-LWR). These new structured Module-LWE and LWR reduce the required number of uniformly random bytes in its matrix by a factor up to the module rank and allow efficient NTT implementations while enabling more granular security-performance trade-offs. We analyze the security of these constructions, provide practical parameter sets, and present implementation results demonstrating a performance improvement of up to 37% compared to an optimized implementation of ML-KEM. Our techniques apply to both key encapsulation mechanisms and digital signature schemes, offering a pathway to more adaptable and performant PQC standards.
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.
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.
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.