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.
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.
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.
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.
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 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.
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.
Post Quantum Key Encapsulation Mechanism (PKEM) is used to securely exchange symmetric keys over an insecure channel. It allows two parties to establish a shared secret key, which can then be used for symmetric encryption, ensuring confidentiality against quantum attacks. By encapsulating the key, it reduces the need to directly encrypt large amounts of data with the public key, which is computationally expensive. Traditional cryptographic tools, while effective, are complex and susceptible to quantum attacks. This paper contains a robust and lightweight post-quantum security solution, and their performance analysis. The authentication scheme, based on Ring-Learning with Errors (Ring-LWE), uses Bernstein reconstruction in polynomial multiplication to significantly lower computational costs, enabling even resource-limited mobile devices to achieve secure mutual authentication. This paper also contains an analysis of post-quantum key encapsulation mechanism (PKEM), and it also covers design, security, and real-world implementation issues and provides a prospective outlook on PKEM, taking into account current investigations, possible innovations, and the changing field of quantum computing. The proposed work also offers a thorough investigation of the security features of post-quantum KEMs, together with theoretical and practical concerns.