論文の概要: Message Recovery Attack in NTRU via Knapsack
- arxiv url: http://arxiv.org/abs/2510.26003v1
- Date: Wed, 29 Oct 2025 22:31:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-31 16:05:09.59235
- Title: Message Recovery Attack in NTRU via Knapsack
- Title（参考訳）: NTRUにおけるKnapsackによるメッセージリカバリ攻撃
- Authors: Eirini Poimenidou, K. A. Draziotis,
- Abstract要約: モジュール型Knapsack問題に基づくメッセージ回復攻撃を導入する。
FLATTER還元は、実際には$epsilonapprox 0.45$でメッセージを回復する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 本稿では,NTRU-HPS暗号システムのすべての変種に適用可能な,モジュール型Knapsack問題に基づくメッセージ回復攻撃を提案する。
メッセージの係数の分数$\epsilon$が${\bf{m}}\in\{-1,0,1\}^N$であり、名詞ベクトル${\bf r}\in\{-1,0,1\}^N$が予めランダムな位置で知られていると仮定すると、モジュラー・ナプサックシステムのインスタンスを符号化する格子内の短いベクトルを見つけるためにメッセージ復号を減少させる。
例えば、${\bf m}$や$({\bf m},{\bf r})$に関する情報は、回復が実現する前に必要か?
FLATTERリダクションは、実際には$\epsilon\approx 0.45$でメッセージを回復する。
私たちの実装では、コモディティデスクトップ上で数分以内に${\bf m}$を見つけます。
関連論文リスト
- Bilinear Compressive Security [4.3725047448751235]
我々は、異なる既知の$x_k$に対して$y$の繰り返し観測から$Q$を回収するために、かなり理想化された既知の攻撃を研究する。
BCSの主な結果によると、フィルタ$h$の対称性の弱い条件下では、$Q$を回収するには、$Omegaleft(maxleft(n,(n/s)2right)$ message $x_k$ if $s$-sparse の送信から広範囲にサンプリングする必要がある。
論文 参考訳（メタデータ） (2025-10-17T07:32:25Z) - From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。
文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。
本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
論文 参考訳（メタデータ） (2025-02-13T12:13:25Z) - Optimal Computational Secret Sharing [51.599517747577266]
$(t, n)$-threshold secret sharingでは、秘密の$S$が$n$の参加者に分散される。
共有サイズが $tfrac|S|t + |K|t$ となる構成を示す。
論文 参考訳（メタデータ） (2025-02-04T23:37:16Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Language Model Inversion [77.22715643068284]
我々は,次の確率が先行するテキストに関する驚くべき量の情報を含んでいることを示す。
我々の反転法は、BLEUが59ドル、トークンレベルのF1が78ドルでプロンプトを再構築し、正確に27%のプロンプトを回収する。
論文 参考訳（メタデータ） (2023-11-22T19:04:04Z) - Public key cryptosystems based on Iterated Functions Systems [2.4374097382908477]
公開鍵が$g$である暗号システムを定義する。
暗号化されるメッセージはワード$wで、関連する暗号文は$Phi_g,w$である。
秘密鍵は$Phi_f,w$を$Phi_g,w$から復元することができる。
論文 参考訳（メタデータ） (2023-09-12T02:12:39Z) - Code-routing: a new attack on position verification [0.0]
$f$-routingとして知られる一般的な検証スキームでは、証明者が量子システムをリダイレクトする必要がある。
我々は、量子システムが秘密共有スキームに符号化される新しい不正行為戦略を提示する。
この戦略は$O(SP_p(f))$ EPRペアを使って$f$-routingタスクを完了する。
論文 参考訳（メタデータ） (2022-02-16T01:04:31Z) - Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。
シミュレーションデータの実験、MovieLens 100KデータセットとYale Bデータベースは、$textM3textOがいくつかのベースラインで最先端のパフォーマンスを達成し、高精度な地上真実対応を回復できることを示した。
論文 参考訳（メタデータ） (2021-10-15T09:27:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。