We consider a key encapsulation mechanism (KEM) based on Module-LWE where reconciliation is performed on the 8-dimensional lattice
E8, which admits a fast CVP algorithm. Our scheme generates 256 bits of key and requires 3 or 4 bits of reconciliation per dimension. We show that it can outperform Kyber in terms of the modulus
qwith comparable error probability and similar requirements in terms of bandwidth. We prove that our protocol is IND-CPA secure and improves the security level of Kyber by 7.3%.
Lattice-based key exchange protocols have attracted tremendous attention for its post-quantum security. In this work, we construct a Module-LWE-based key exchange protocol using Peikert’s error reconciliation mechanism. Compared with Kyber.KE, our key exchange protocol reduces the total communication cost by 96-byte, i.e., 3.2% ∼ 6.1%, under the different parameter sets, and without reducing the post-quantum security levels. Moreover, our key exchange protocol slightly reduces the probability of session key agreement failure and the time consumed by modular multiplication of numbers and ring elements by approximately 30%. Thus, the key exchange protocol in this paper is more suitable for the lightweight communication systems.
The widespread use of Internet of Things devices alongside advances in quantum computing presents urgent challenges for secure communication. RSA and ECC have become inadequate, prompting the need for Post-quantum Cryptography (PQC). This work introduces a novel reconciliation-based Module-LWE key exchange protocol that eliminates the traditional encapsulation-decapsulation structure in schemes like Kyber.KE, thereby reducing computational cycles, communication size, and memory footprint. Unlike Kyber and NewHope, the proposed design employs modular rounding with Peikert reconciliation, optimizing the entire key exchange process without requiring additional randomness or ciphertext transmission. By leveraging Peikert’s error reconciliation technique and modular rounding, the proposed protocol achieves a 15% reduction in computational cycles, a 78-byte reduction in communication size, and a 10% decrease in memory usage. Using Open Quantum Safe (OQS) benchmark data, we evaluate performance across Kyber512, Kyber768, and Kyber1024 levels, demonstrating the protocol’s superior energy efficiency and lightweight design. These improvements position our protocol as a secure, efficient, and scalable solution for post-quantum key exchange in resource-constrained environments such as embedded systems and IoT networks.
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 the
E8lattice is optimal in the sense of the best density for sphere packing in
R8. 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.
Module Learning with Errors (M-LWE) based key reconciliation mechanisms (KRM) can be viewed as quantizing an M-LWE sample according to a lattice codebook. This paper describes a generic M-LWE-based KRM framework, valid for any dimensional lattices and any modulus
qwithout a dither. Our main result is an explicit upper bound on the decryption failure rate (DFR) of M-LWE-based KRM. This bound allows us to construct optimal lattice quantizers to reduce the DFR and communication cost simultaneously. Moreover, we present a KRM scheme using the same security parameters
(q,k,η1,η2)as in Kyber. Compared with Kyber, the communication cost is reduced by up to 36.47% and the DFR is reduced by a factor of up to 299. The security arguments remain the same as Kyber.