In the present paper, we introduce a message-recovery attack based on the Modular Knapsack Problem, applicable to all variants of the NTRU-HPS cryptosystem. Assuming that a fraction \(\epsilon \) of the coefficients of the message m \(\in \{-1,0,1\}^N\) and of the nonce vector \(\textbf{r} \in \) \(\{-1,0,1\}^N\) are known in advance at random positions, we reduce message decryption to finding a short vector in a lattice that encodes an instance of a modular knapsack system. This allows us to address a key question: how much information about \(\textbf{m},\) or about the pair \((\textbf{m},\textbf{r}),\) is required before recovery becomes feasible? A FLATTER reduction successfully recovers the message, in practice when \(\epsilon \approx 0.45.\) Our implementation finds \(\textbf{m}\) within a few minutes on a commodity desktop.
