Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Forensics and Security

Cryptanalysis on “NTRU+: Compact Construction of NTRU Using Simple Encoding Method”

Joohee Lee, Hansol Ryu, Minju Lee, Jaehui Park

Published Jan 1, 2024• 1 citation
Publisher

Abstract

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.

DOI
10.1109/tifs.2024.3471074

Related papers

BAT: Small and Fast KEM over NTRU Lattices

Pierre-Alain Fouque, Paul Kirchner, Thomas Pornin +1 more

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.

IACR Transactions on Cryptographic Hardware and Embedded Systems•Feb 15, 2022•24 citations

Compact and Efficient KEMs over NTRU Lattices

Zhichuang Liang, Boyue Fang, Zheng, Jieyu +1 more

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.

arXiv:2205.05413•May 11, 2022•1 citation

Efficient chosen ciphertext secure key encapsulation mechanism in standard model over ideal lattices

Xiaopeng Yang, Wenping Ma, Chengli Zhang

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.

International Journal of Computer Mathematics•Feb 6, 2016•4 citations

Indistinguishability under adaptive chosen-ciphertext attack secure double-NTRU-based key encapsulation mechanism

Kübra Seyhan, Sedat Akleylek

In this article, we propose a double-NTRU (D-NTRU)-based key encapsulation mechanism (KEM) for the key agreement requirement of the post-quantum world. The proposed KEM is obtained by combining one-way D-NTRU encryption and Dent's KEM design method. The main contribution of this article is to construct a D-NTRU-based KEM that provides indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2) security. The IND-CCA2 analysis and primal/dual attack resistance of the proposed D-NTRU KEM are examined in detail. A comparison with similar protocols is provided regarding parameters, public/secret keys, and ciphertext sizes. The proposed scheme presents arithmetic simplicity and IND-CCA2 security that does not require any padding mechanism.

PeerJ Computer Science•May 26, 2023•5 citations

A Concrete LIP-Based KEM With Simple Lattices

Gustavo de Castro Biage, Gustavo Zambonin, Thaís Bardini Idalino +2 more

Recent developments have been made in the construction of cryptosystems with security based on the hardness of the lattice isomorphism problem (LIP). Due to lattice conjectures, one may expect in the future that breaking such schemes is computationally harder than most current lattice-based cryptosystems. To the best of our knowledge, there have not been any attempts to concretely instantiate a key encapsulation mechanism (KEM) based on LIP. In this work, we propose the first instance of such a KEM, following the framework of Ducas and van Woerden (EUROCRYPT 2022), using simple lattices. We present a randomness extractor derived from a hash function based on the short integer solution problem; define a concrete set of parameters for instantiating the scheme; provide a rigorous security estimation of an attacker trying to decode an encapsulated key through reductions to hard lattice problems; and use well-known methods to convert the IND-CPA secure KEM into an IND-CCA2 secure KEM, comparing the latter with other modern lattice-based KEMs. The resulting security is estimated under the assumption that an adversary cannot efficiently solve related instances of LIP, which is a consequence of the lack of cryptanalysis towards identifying isomorphism between lattices.

IEEE Access•Jan 1, 2024•5 citations

A Lattice-Based Hybrid Encryption Framework for Post-Quantum Security

Revathy M, D D, Natarajan K

RSA and ECC cryptography methods are classical methods based on the complexity of integer factorization and discrete logarithm problems, but these are in earnest danger due to the rapid advancements in quantum computing. Lattice-based encryption has also emerged as a post-quantum candidate encryption scheme in response to these weaknesses, because of its proven ability to resist quantum attacks. To ensure a safe and efficient transmission of data, the current study provides a lattice-based hybrid encryption model with the combination of two popular post-quantum schemes, NTRU and Kyber. The proposed system provides a powerful two-way key exchange and encryption system, based on a lattice-based key encapsulation mechanism (KEM) introduced by Kyber and the polynomial-based public key encryption introduced by NTRU. To ensure the safety of the exchange of key data, the actual message data is encrypted using a symmetric cipher known as AES (Advanced Encryption Standard), and the exchange of the session key is safely performed with the help of the hybrid NTRU Kyber framework. Using this method, we achieve high computing efficiency, forward secrecy, and resistance to quantum attacks. The project demonstrates the benefits of applying the lattice-based techniques in enhancing the overall security posture of encrypted communications by simulating and executing the techniques. The research results indicate the importance of hybrid post-quantum systems in the development of cryptographic systems that are resistant to novel quantum attacks.

International Conference on Secure Cyber Computing and Communications (ICSCCC)•May 29, 2026•0 citations
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.
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%12\%12% smaller ciphertext size while encapsulating 384-bit keys compared to the fixed 256-bit key size of Kyber, security strengthened by (8,7)(8,7)(8,7) bits for classical and quantum security respectively, and significantly lower error probability (2−2302^{-230}2−230 of CNTR-768 vs. 2−1642^{-164}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%15\%15% smaller ciphertext size, and the security is strengthened by (55,49)(55,49)(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.
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.
In this article, we propose a double-NTRU (D-NTRU)-based key encapsulation mechanism (KEM) for the key agreement requirement of the post-quantum world. The proposed KEM is obtained by combining one-way D-NTRU encryption and Dent's KEM design method. The main contribution of this article is to construct a D-NTRU-based KEM that provides indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2) security. The IND-CCA2 analysis and primal/dual attack resistance of the proposed D-NTRU KEM are examined in detail. A comparison with similar protocols is provided regarding parameters, public/secret keys, and ciphertext sizes. The proposed scheme presents arithmetic simplicity and IND-CCA2 security that does not require any padding mechanism.
Recent developments have been made in the construction of cryptosystems with security based on the hardness of the lattice isomorphism problem (LIP). Due to lattice conjectures, one may expect in the future that breaking such schemes is computationally harder than most current lattice-based cryptosystems. To the best of our knowledge, there have not been any attempts to concretely instantiate a key encapsulation mechanism (KEM) based on LIP. In this work, we propose the first instance of such a KEM, following the framework of Ducas and van Woerden (EUROCRYPT 2022), using simple lattices. We present a randomness extractor derived from a hash function based on the short integer solution problem; define a concrete set of parameters for instantiating the scheme; provide a rigorous security estimation of an attacker trying to decode an encapsulated key through reductions to hard lattice problems; and use well-known methods to convert the IND-CPA secure KEM into an IND-CCA2 secure KEM, comparing the latter with other modern lattice-based KEMs. The resulting security is estimated under the assumption that an adversary cannot efficiently solve related instances of LIP, which is a consequence of the lack of cryptanalysis towards identifying isomorphism between lattices.
RSA and ECC cryptography methods are classical methods based on the complexity of integer factorization and discrete logarithm problems, but these are in earnest danger due to the rapid advancements in quantum computing. Lattice-based encryption has also emerged as a post-quantum candidate encryption scheme in response to these weaknesses, because of its proven ability to resist quantum attacks. To ensure a safe and efficient transmission of data, the current study provides a lattice-based hybrid encryption model with the combination of two popular post-quantum schemes, NTRU and Kyber. The proposed system provides a powerful two-way key exchange and encryption system, based on a lattice-based key encapsulation mechanism (KEM) introduced by Kyber and the polynomial-based public key encryption introduced by NTRU. To ensure the safety of the exchange of key data, the actual message data is encrypted using a symmetric cipher known as AES (Advanced Encryption Standard), and the exchange of the session key is safely performed with the help of the hybrid NTRU Kyber framework. Using this method, we achieve high computing efficiency, forward secrecy, and resistance to quantum attacks. The project demonstrates the benefits of applying the lattice-based techniques in enhancing the overall security posture of encrypted communications by simulating and executing the techniques. The research results indicate the importance of hybrid post-quantum systems in the development of cryptographic systems that are resistant to novel quantum attacks.