We present BAT – an IND-CCA secure key encapsulation mechanism (KEM) that is based on NTRU but follows an encryption/decryption paradigm distinct from classical NTRU KEMs. It demonstrates a new approach of decrypting NTRU ciphertext since its introduction 25 years ago. Instead of introducing an artificial masking parameter p to decrypt the ciphertext, we use 2 linear equations in 2 unknowns to recover the message and the error. The encryption process is therefore close to the GGH scheme. However, since the secret key is now a short basis (not a vector), we need to modify the decryption algorithm and we present a new NTRU decoder. Thanks to the improved decoder, our scheme works with a smaller modulus and yields shorter ciphertexts, smaller than RSA-4096 for 128-bit classical security with comparable public-key size and much faster than RSA or even ECC. Meanwhile, the encryption and decryption are still simple and fast in spite of the complicated key generation. Overall, our KEM has more compact parameters than all current lattice-based schemes and a practical efficiency. Moreover, due to the similar key pair structure, BAT can be of special interest in some applications using Falcon signature that is also the most compact signature in the round 3 of the NIST post-quantum cryptography standardization. However, different from Falcon, our KEM does not rely on floating-point arithmetic and can be fully implemented over the integers.
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.
In post-quantum cryptography, recently many interesting works were done to improve the efficiency of Public Key Encryption (PKE) and Key Encapsulation Management (KEM) schemes based on NTRU (ANTS '98) lattices by reducing the size of the ciphertext (ct) and the public key (pk), and also by improving the speed of the associated algorithms: BAT (TCHES, 2022), NTTRU (TCHES, 2019) and it's generalization (called here NTRU-ABC) by Duman et al (PKC, 2023), NEV (ASIACRYPT 2023), NTRU+ (IEEE, 2023), CTRU and CNTR (Science Direct 2023). In Module-Falcon signature paper (ASIA CCS 2020), a public key encryption based on MNTRU was proposed but its efficiency was not better than existing schemes as said by their authors. In this work, we propose EagleTru, a new family of MNTRU and NTRU based PKEs and KEMs. The public key is H = D(pG) -1 mod ± q ∈ R l×l q where gcd(p, q) = 1, G is a square matrix invertible in R l×l q
In this paper, we present CTRU-Light, an IND-CCA-secure key encapsulation mechanism (KEM) derived from NTRU and RLWE (and RLWR in variant) assumptions over power-of-two cyclotomic rings. Our CTRU-Light employs a compact NTT-compatible modulus q=641 while maintaining minimal public key and ciphertext dimensions with negligible error probability. Specifically, the design yields public key and ciphertext sizes of 1206 bytes under an error probability bound of ≤2−110. When benchmarked against Kyber (NIST’s sole standardized KEM), CTRU-Light demonstrates 23.0–30.0% lower bandwidth consumption, accelerates key generation by at least 6.0%, and achieves over 1.3× speed enhancement in both encapsulation and decapsulation procedures.
In IEEE TIFS 2023, NTRU+ has been proposed, an efficient lattice-based post-quantum Key Encapsulation Mechanism (KEM), which has also been submitted to the KpqC competition. In this paper, we propose an effective classical chosen ciphertext attack to recover the transmitted session key for NTRU+ with all but negligible probability for the first time. With the proposed attacks, we show that all the suggested parameters of NTRU+ do not satisfy the claimed IND-CCA security. Moreover, we elaborate on some flaws in the security proof, a part of which introduces our attack. We also suggest a way to modify the NTRU+ scheme to defend our attack while maintaining its practical performance.
Key encapsulation mechanism (KEM) is an important key distribution mechanism that not only allows both sender and receiver to safely share a random session key, but also can be mainly applied to construct a hybrid public key encryption scheme. In this paper, we give an positive answer to the question of if it is possible to build an efficient KEM over lattices. More precisely, we design an efficient KEM scheme in standard model based on ideal lattices. We prove that the proposed scheme captures indistinguishability against active chosen ciphertext attacks (IND-CCA) under the ring learning with errors problem, or more formally, IND-CCA security. Compared with the current CCA secure KEM schemes based on lattices in the standard model, our scheme has shorter public key, secret key and encapsulation ciphertext. In addition, our KEM scheme realizes IND-CCA security in the standard model.
Based on the NTRU trapdoor used in NIST's Falcon, a signcryption scheme following the sign-then-encrypt paradigm is constructed. The existing partitioning technique based on Waters hash over the lattice can not complete the security reduction in the standard model for the signature part due to the "partiality" of the pre-image generated with the NTRU trapdoor. To address this, a variant of Waters hash over small integers is proposed and, the probability of the successful reduction is analyzed. The resulting signcryption achieves existential unforgeability under the adaptive chosen-message attacks. By utilizing the uniqueness of the secret and the noise in an NTRU instance, the tag used in encryption is eliminated. Furthermore, a method to construct tamper-sensitive lattice public key encryption is proposed. This approach implants the ciphertext-sensitive information into the lattice public key encryption and binds it to the encrypted information. The malleability to the public key ciphertext triggers the change of the message-signature pair so that the IND-CCA2 security of the entire ciphertext can be guaranteed by the signature for the message. Thanks to the rational design and the efficiency of the NTRU trapdoor, the computational overhead of the proposed scheme is reduced significantly compared to the existing lattice-based signcryption scheme, reaching orders of magnitude improvement in efficiency. The experiment shows that the proposed scheme is efficient.