Message Recovery Attack in NTRU via Knapsack
Eirini Poimenidou, K. A. Draziotis · 2025
Read Message Recovery Attack in NTRU via Knapsack by Eirini Poimenidou, K. A. Draziotis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26003.txt.
Introduction
Eirini Poimenidou and K. A. Draziotis present an attack that can recover a secret message from the NTRU-HPS cryptosystem when part of the message is already known. NTRU is a lattice based encryption scheme designed to resist quantum attacks. Their attack assumes a fraction of the message and nonce coefficients, each drawn from minus one, zero, and one, are known at random positions in advance.
Poimenidou and Draziotis turn decryption into a modular knapsack problem, a packing puzzle with a remainder condition, then encode it as a short vector search in a lattice. A lattice reduction tool recovered the message in practice when the known fraction was near forty five percent, within minutes on a desktop in their tests.
Catalog record
| CREATOR | Eirini Poimenidou, K. A. Draziotis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-26003
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Message Recovery Attack in NTRU via Knapsack Eirini Poimenidou, K. A. Draziotis 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 ϵ \epsilon of the coefficients of the message 𝐦 ∈ { − 1 , 0 , 1 } N {\bf{m}}\in\{-1,0,1\}^{N} and of the nonce vector 𝐫 ∈ { − 1 , 0 , 1 } N {\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 ϵ ≈ 0.45 \epsilon\approx 0.45 . Our implementation finds 𝐦 {\bf m} within a few minutes on a commodity desktop. 2020 Mathematics Subject Classification 94A60 1. Introduction In 1996, Hoffstein, Pipher, and Silverman developed the NTRU cryptosystem, aiming to create robust encryption and signature systems, as detailed in [ 18 ] . Its security is based on the difficulty of solving a system of linear equations over polynomial rings, a problem that is expected to remain hard even with quantum computers. NTRU cryptosystem has withstood over 25 years of cryptanalysis, and variants of it NTRU have been shown to be closely related to the Ring Learning With Errors (R-LWE) problem, whose hardness is supported by worst-case reductions on ideal lattices. NTRU is known for its exceptional performance and moderate key-size, making it a popular choice for embedded cryptography. It has been standardized by IEEE, X9.98, and PQCRYPTO, and was a finalist in the NIST post-quantum cryptography standardization effort. In the present work, we outline a message recovery attack on NTRU based on the Shortest Vector Problem (SVP). Our method assumes partial knowledge of the message {\bf m}\in\{-1,0,1\}^{N} and/or of the nonce vector {\bf r}\in\{-1,0,1\}^{N} . Such leakage assumptions are standard in the literature: for example, several works on DSA [ 2 , 3 , 20 ] recover secret keys by exploiting partial information about ephemeral keys. In [ 30 ] , the authors use ”hints” from an oracle to recover the secret key in Kyber. Also, Coppersmith type attacks assume some knowledge of the one prime in order to compute the remaining part. 1.1. Previous Work The NTRU cryptosystem was first subjected to a lattice-based attack in 1997 by Coppersmith and Shamir [ 9 ] . Later, Gama and Nguyen [ 14 ] exploited decryption failures to recover the secret key, under the assumption of access to a decryption oracle. Subsequently, in 2001, Gentry [ 16 ] proposed an attack that is particularly effective when the parameter N is composite. A number of other approaches have been developed to attack NTRU. One notable line of work reformulates the NTRU problem as a system of multivariate quadratic equations over the binary field, utilizing Witt vectors [ 7 , 40 ] . Odlyzko [ 21 ] proposed a meet-in-the-middle strategy that partitions the search space into two halves, reducing time complexity at the cost of substantial memory usage. Building on this idea, Howgrave-Graham introduced a hybrid attack [ 19 ] that combines lattice reduction with a meet-in-the-middle approach. This hybrid technique has since become a standard method for assessing the security of lattice-based encryption schemes. For NTRU variants operating under larger moduli than those used in the NTRUEncrypt standard, Albrecht, Bai, and Ducas [ 5 ] , as well as Cheon, Jeong, and Lee [ 11 ] , independently extended and refined these hybrid and meet-in-the-middle techniques to remain effective in more demanding parameter regimes. Nguyen [ 33 ] later enhanced these methods by clarifying their structure and further improving their efficiency. While the subfield attack proposed in the previous work surpasses several earlier strategies, it still falls short of the most advanced hybrid attacks in terms of performance. More recently, in 2023, May and Nowakowski [ 26 ] introduced a powerful new attack on the latest NTRU encryption scheme. Their approach employs a carefully designed lattice, leveraging the BKZ algorithm in conjunction with the sieving methods from the G6K library. Transitioning away from the traditional Coppersmith-Shamir lattice, they construct a lattice based on the cyclotomic ring, achieving significant performance gains. Finally, in 2025, two message recovery attacks [ 4 , 35 ] based on Babai nearest plane algorithm are presented. The authors of [ 34 ] also implement a message recovery attack, after reducing the NTRU-lattice to a Voronoi First Kind (VFK) lattice and then use a polynomial exact CVP-algorithm to recover the message. 1.2. Our contribution In this paper we aim to recover the unknown message. We consider an adversary who observes ciphertexts of the NTRU-HPS encryption scheme and who is assumed to know k coefficients of the ternary plaintext polynomial m(x)\in\{-1,0,1\}^{N} or k_{1} coefficients of m(x) and k_{2} coefficients of the unknown nonce r(x)\in\{-1,0,1\}^{N} . More precisely, knowledge of approximately 45\% of the coefficients of the pair of unknown polynomials (m(x),r(x)) , suffices to reconstruct r(x) and, consequently, recover the plaintext m(x) . Such partial information may be leaked via a side-channel, arise from protocol redundancy, or be exposed by format markers. Our method differs from previous approaches [ 4 , 34 , 35 ] , as it relies on the Shortest Vector Problem (SVP) rather than the Closest Vector Problem (CVP) . The SVP is better understood, both theoretically and algorithmically, providing a more solid foundation for our analysis. Our assumptions in the present work are clearer, as it involves only the message polynomial m(x) and the nonce r(x) . Moreover, the underlying problem we attack is different. In our attack we solve a modular knapsack with coefficients in \{-1,0,1\} (instead of \{0,1\} ). In more details our method reduces to the following problem: Let a matrix A\in\mathbb{Z}_{q}^{n\times m} and a vector B\in\mathbb{Z}_{q}^{n\times 1} , we seek a vector X with entries in \{-1,0,1\}, \text{such that}\ A\,X=B\ \text{in}\ \mathbb{Z}_{q}. We call this modular knapsack problem , also known as Inhomogeneous Short Integer Solution problem ( ISIS_{q} [ 13 ] ). Furthermore, the present paper contributes to the study of the previous problem both in theory and in practice. Finally, our attack can also be applied to the NTRU-HRSS scheme, where only its parameters would need to change. For NTRU-Prime our attack could also be effective, however more research is required since it employs a non cyclic linear system which is different from the system in our case. 1.3. Plausibility of Partial-Plaintext Knowledge In a Key Encapsulation Mechanism (KEM) the message {\bf m} is ideally sampled uniformly at random, however if an implementation instead derives {\bf m} (or the Key Derivation Function (KDF) preimage) from a structured seed, large portions of its content may be predictable. Additionally, if a weak pseudorandom number generator (PRNG) is used, then an adversary who collects sufficiently many (\mathbf{m}_{i},\mathbf{c}_{i}) pairs can detect statistical biases in certain coefficients of {m}_{i} and exploit them to recover partial information. In [ 22 ] the authors