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.

In this paper, we describe a polynomial time cryptanalysis of the (approximate) multilinear map proposed by Coron, Lepoint, and Tibouchi in Crypto13 (CLT13). This scheme includes a zero-testing functionality that determines whether the message of a given encoding is zero or not. This functionality is useful for designing several of its applications, but it leaks unexpected values, such as linear combinations of the secret elements. By collecting the outputs of the zero-testing algorithm, we construct a matrix containing the hidden information as eigenvalues, and then recover all the secret elements of the CLT13 scheme via diagonalization of the matrix. In addition, we provide polynomial time algorithms to directly break the security assumptions of many applications based on the CLT13 scheme. These algorithms include solving subgroup membership, decision linear, and graded external Diffie–Hellman problems. These algorithms mainly rely on the computation of the determinants of the matrices and their greatest common divisor, instead of performing their diagonalization.