Message Recovery Attack in NTRU via Knapsack

• URL: http://arxiv.org/abs/2510.26003v1
• Date: Wed, 29 Oct 2025 22:31:33 GMT
• Title: Message Recovery Attack in NTRU via Knapsack
• Authors: Eirini Poimenidou, K. A. Draziotis,
• Abstract summary: We introduce a message-recovery attack based on the Modular Knapsack Problem.<n>A FLATTER reduction successfully recovers the message, in practice when $epsilonapprox 0.45$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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 ${\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 $\epsilon\approx 0.45$. Our implementation finds ${\bf m}$ within a few minutes on a commodity desktop.

Related papers

• What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements [42.543830499945926]
  We seek the smallest set containing $xstar$--that is uniformly recoverable from $y$ without knowing $e$.<n>Our main result shows that the best that one can hope to recover is $xstar + ker(U)$, where $U$ is the unique projection matrix onto the intersection of rowspaces of all possible submatrices of $A$ obtained by deleting $2q$ rows.
  arXiv  Detail & Related papers  (2025-10-28T09:29:46Z)
• Bilinear Compressive Security [4.3725047448751235]
  We study a rather idealized known attack for recovering $Q$ from repeated observations of $y$'s for different, known $x_k$.<n>Our main result for BCS states that under a weak symmetry condition on the filter $h$, recovering $Q$ will require extensive sampling from transmissions of $Omegaleft(maxleft(n,(n/s)2right)$ messages $x_k$ if they are $s$-sparse.
  arXiv  Detail & Related papers  (2025-10-17T07:32:25Z)
• Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update [62.96781471194877]
  Two principled strategies for handling heavy-tailed noise, truncation and median-of-means, have been introduced to heavy-tailed bandits.<n>We propose a emphone-pass algorithm based on the online mirror descent framework.
  arXiv  Detail & Related papers  (2025-03-01T09:41:45Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  We study the problem of contextual semi-bandits, where input contexts are mapped into subsets of size $m$ of a collection of $K$ possible actions.<n>Motivated by prototypical applications of contextual bandits, we focus on the $s$-sparse regime.<n>Our framework generalizes the list multiclass classification problem with bandit feedback, which can be seen as a special case with binary reward vectors.
  arXiv  Detail & Related papers  (2025-02-13T12:13:25Z)
• Optimal Computational Secret Sharing [51.599517747577266]
  In $(t, n)$-threshold secret sharing, a secret $S$ is distributed among $n$ participants.<n>We present a construction achieving a share size of $tfrac|S|t + |K|t$.
  arXiv  Detail & Related papers  (2025-02-04T23:37:16Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Language Model Inversion [77.22715643068284]
  We show that next-token probabilities contain a surprising amount of information about the preceding text. Our inversion method reconstructs prompts with a BLEU of $59$ and token-level F1 of $78$ and recovers $27%$ of prompts exactly.
  arXiv  Detail & Related papers  (2023-11-22T19:04:04Z)
• Public key cryptosystems based on Iterated Functions Systems [2.4374097382908477]
  We define a cryptosystem whose public key is$g$. The message to be encrypted is a word$w and the associated cryptogram is $Phi_g,w$. The private key allows to recover $Phi_f,w$ from $Phi_g,w$.
  arXiv  Detail & Related papers  (2023-09-12T02:12:39Z)
• Invertible Bloom Lookup Tables with Less Memory and Randomness [23.724300017513574]
  Invertible Bloom Lookup Tables (IBLTs) have found applications in set reconciliation protocols, error-correcting codes, and the design of advanced cryptographic primitives.<n>We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness.<n>We show that hashing $n$ keys with any $k$-wise independent hash function $h:U to [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1 - 2-Omega(k)$ that at least $n/2$ keys will have a unique hash value
  arXiv  Detail & Related papers  (2023-06-13T07:15:02Z)
• Code-routing: a new attack on position verification [0.0]
  A popular verification scheme known as $f$-routing involves requiring the prover to redirect a quantum system. We give a new cheating strategy in which the quantum system is encoded into a secret-sharing scheme. This strategy completes the $f$-routing task using $O(SP_p(f))$ EPR pairs.
  arXiv  Detail & Related papers  (2022-02-16T01:04:31Z)
• Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
  We show that it is possible to recover $M$ via solving a nuclear norm minimization problem under a proper low-rank condition on $M$, with provable non-asymptotic error bound for the recovery of $M$. Experiments on simulated data, the MovieLens 100K dataset and Yale B database show that $textM3textO achieves state-of-the-art performance over several baselines and can recover the ground-truth correspondence with high accuracy.
  arXiv  Detail & Related papers  (2021-10-15T09:27:50Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  We study efficient estimation and detection of a planted vector $v$ whose $ell_4$ norm differs from that of a Gaussian vector with the same $ell$ norm. We show that in the regime $n rho gg sqrtN$, any spectral method from a large class (and more generally, any low-degree of the input) fails to detect the planted vector.
  arXiv  Detail & Related papers  (2021-05-31T16:10:49Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.