Message Recovery Attack in NTRU via Knapsack
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918178527903744 |
|---|---|
| author | Poimenidou, Eirini Draziotis, K. A. |
| author_facet | Poimenidou, Eirini Draziotis, K. A. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26003 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Message Recovery Attack in NTRU via Knapsack Poimenidou, Eirini Draziotis, K. A. Cryptography and Security 94A60 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. |
| title | Message Recovery Attack in NTRU via Knapsack |
| topic | Cryptography and Security 94A60 |
| url | https://arxiv.org/abs/2510.26003 |