{"ID":2848804,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.26003","arxiv_id":"2510.26003","title":"Message Recovery Attack in NTRU via Knapsack","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 ${\\bf{m}}\\in\\{-1,0,1\\}^N$ and of the nonce vector ${\\bf 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 ${\\bf m}$, or about the pair $({\\bf m},{\\bf r})$, is required before recovery becomes feasible? A FLATTER reduction successfully recovers the message, in practice when $ε\\approx 0.45$. Our implementation finds ${\\bf m}$ within a few minutes on a commodity desktop.","short_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 ${\\bf{m}}\\in\\{-1,0,1\\}^N$ and of the nonce vector ${\\bf r}\\in\\{-1,0,1\\}^N$ are known in advance at...","url_abs":"https://arxiv.org/abs/2510.26003","url_pdf":"https://arxiv.org/pdf/2510.26003v1","authors":"[\"Eirini Poimenidou\",\"K. A. Draziotis\"]","published":"2025-10-29T22:31:33Z","proceeding":"cs.CR","tasks":"[\"cs.CR\"]","methods":"[]","has_code":false}