Message recovery attack in NTRU through VFK lattices

In the present paper, we introduce a message recovery attack applicable to NTRU cryptosystem. Our methodology uses a reduction from the NTRU-lattice to a Voronoi First Kind (VFK) lattice, enabling the use of a polynomial Closest Vector Problem (CVP) exact algorithm, which is vital for successful message recovery. This approach assumes knowledge of the Most Significant Bit of the coefficients of a polynomial that is a multiple of the nonce. Finally, extensive experimental results for the NTRU-HPS variants submitted to NIST are presented. The findings highlight the need to properly protect NTRU schemes against potential leakage.