Abstract
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 ε of the coefficients of the message m∈{-1,0,1}^N and of the nonce vector r∈{-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 m, or about the pair ( m, r), is required before recovery becomes feasible? A FLATTER reduction successfully recovers the message, in practice when ε≈ 0.45. Our implementation finds m within a few minutes on a commodity desktop.