論文の概要: The cool and the cruel: separating hard parts of LWE secrets

• arxiv url: http://arxiv.org/abs/2403.10328v2
• Date: Thu, 10 Oct 2024 14:57:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-11 14:27:30.807991
• Title: The cool and the cruel: separating hard parts of LWE secrets
• Title（参考訳）: 冷静で残酷な―LWEシークレットの硬い部分を切り離す
• Authors: Niklas Nolte, Mohamed Malhou, Emily Wenger, Samuel Stevens, Cathy Li, François Charton, Kristin Lauter,
• Abstract要約: スパースバイナリLWEシークレットに対する既知の攻撃には、スパースデュアルアタックとミドルアタックにおけるハイブリッドスパースデュアルミートが含まれる。 本稿では,メモリ要求の少ない新しい統計的攻撃を提案する。
• 参考スコア（独自算出の注目度）: 11.000531626756853
• License:
• Abstract: Sparse binary LWE secrets are under consideration for standardization for Homomorphic Encryption and its applications to private computation. Known attacks on sparse binary LWE secrets include the sparse dual attack and the hybrid sparse dual-meet in the middle attack which requires significant memory. In this paper, we provide a new statistical attack with low memory requirement. The attack relies on some initial lattice reduction. The key observation is that, after lattice reduction is applied to the rows of a q-ary-like embedded random matrix $\mathbf A$, the entries with high variance are concentrated in the early columns of the extracted matrix. This allows us to separate out the "hard part" of the LWE secret. We can first solve the sub-problem of finding the "cruel" bits of the secret in the early columns, and then find the remaining "cool" bits in linear time. We use statistical techniques to distinguish distributions to identify both the cruel and the cool bits of the secret. We provide concrete attack timings for recovering secrets in dimensions $n=256$, $512$, and $768$. For the lattice reduction stage, we leverage recent improvements in lattice reduction (e.g. flatter) applied in parallel. We also apply our new attack in the RLWE setting for $2$-power cyclotomic rings, showing that these RLWE instances are much more vulnerable to this attack than LWE.
• Abstract（参考訳）: スパースバイナリLWEシークレットは、ホモモルフィック暗号化の標準化とそのプライベート計算への応用について検討されている。 スパースバイナリLWEシークレットに対する攻撃として、スパースデュアルアタック(sparse dual attack)や、大きなメモリを必要とする中間攻撃におけるハイブリッドスパースデュアルミート( hybrid sparse dual-meet)がある。 本稿では,メモリ要求の少ない新しい統計的攻撃を提案する。 この攻撃は、初期の格子の縮小に依存している。 鍵となる観察は、q-aryのような埋め込みランダム行列 $\mathbf A$ の行に格子還元を適用すると、高い分散を持つエントリは抽出された行列の早期列に集中するということである。 これにより、LWEシークレットの"ハード部分"を分離することができます。 まず、初期列の秘密の「クレル」ビットを見つけるというサブ確率を解き、残りの「クール」ビットを線形時間で見つけることができる。 統計的手法を用いて分布を識別し、秘密の残酷な部分とクールな部分の両方を識別する。 シークレットを次元$n=256$,512$,768$で回収するための具体的な攻撃タイミングを提供する。 格子還元段階において、格子還元(例えば平ら化)の最近の改良を並列に適用する。 また、このRLWEインスタンスがLWEよりもはるかに脆弱であることを示すために、RLWE設定に2ドルパワーのサイクロトミックリングを適用した。

関連論文リスト

• Benchmarking Attacks on Learning with Errors [9.031051362571436]
  誤りを伴う学習(LWE)に基づく格子暗号スキームは、後量子暗号システムとして使われるためにNISTによって標準化されている。 標準化されたパラメータのLWEシークレットリカバリのための最初のベンチマークを、小さくて低ウェイトな(スパースな)シークレットに対して提供します。 SALSAとCool & Cruelの攻撃を大きな形で拡張し、MitM攻撃の実装とスケールアップを初めて行います。
  論文  参考訳（メタデータ） (2024-08-01T19:21:20Z)
• Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors [10.800552110718714]
  LWE(Learning with Errors)は、鍵交換とデジタル署名のための量子後暗号システムの基礎となる難解な数学問題である。 以前の作業では、小さな秘密を持つLWE問題に対する機械学習(ML)ベースの新たな攻撃を提案したが、これらの攻撃には、秘密をトレーニングし、回復するのに数日を要する数百万のLWEサンプルが必要である。 我々は、これらの攻撃を改善するために、3つの重要な方法、より良い前処理、角埋め込み、モデル事前訓練を提案する。
  論文  参考訳（メタデータ） (2024-02-02T00:48:27Z)
• SmoothLLM: Defending Large Language Models Against Jailbreaking Attacks [99.23352758320945]
  SmoothLLMは,大規模言語モデル(LLM)に対するジェイルブレーキング攻撃を軽減するために設計された,最初のアルゴリズムである。 敵が生成したプロンプトが文字レベルの変化に対して脆弱であることから、我々の防衛はまず、与えられた入力プロンプトの複数のコピーをランダムに摂動し、対応する予測を集約し、敵の入力を検出する。
  論文  参考訳（メタデータ） (2023-10-05T17:01:53Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• SALSA PICANTE: a machine learning attack on LWE with binary secrets [8.219373043653507]
  スパースバイナリシークレットを用いたLWEに対する強化機械学習攻撃であるPICANTEを提案する。 PICANTEは、より大きな次元(最大$n=350$)で秘密を回収し、より大きなハミング重みを持つ。 PICANTEはNISTのLWE標準を脅かしていないが、SALSAよりも大幅に改善されている。
  論文  参考訳（メタデータ） (2023-03-07T19:01:01Z)
• Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression [65.8785736964253]
  本稿では,線形制約付きコンテキスト帯域(CBwLC)について考察する。これは,アルゴリズムが全消費の線形制約を受ける複数のリソースを消費するコンテキスト帯域の変種である。 この問題はknapsacks (CBwK) を用いてコンテキスト的帯域幅を一般化し、制約のパッケージ化とカバー、および正および負のリソース消費を可能にする。 本稿では,回帰オラクルに基づくCBwLC(CBwK)のアルゴリズムについて述べる。このアルゴリズムは単純で,計算効率が良く,統計的に最適である。
  論文  参考訳（メタデータ） (2022-11-14T16:08:44Z)
• Hindering Adversarial Attacks with Implicit Neural Representations [25.422201099331637]
  Lossy Implicit Network Activation Coding (LINAC) の防衛は、いくつかの共通の敵攻撃を妨害する。 鍵ベース防衛のためのパラメトリックバイパス近似(PBA)攻撃戦略を考案し,このカテゴリにおける既存手法の無効化に成功した。
  論文  参考訳（メタデータ） (2022-10-22T13:10:24Z)
• PDPGD: Primal-Dual Proximal Gradient Descent Adversarial Attack [92.94132883915876]
  最先端のディープニューラルネットワークは、小さな入力摂動に敏感である。 対向騒音に対するロバスト性を改善するための多くの防御法が提案されている。 敵の強靭さを評価することは 極めて困難であることが分かりました
  論文  参考訳（メタデータ） (2021-06-03T01:45:48Z)
• Limitations on Uncloneable Encryption and Simultaneous One-Way-to-Hiding [17.660958043781154]
  古典的メッセージに対する不必要な量子暗号方式について検討する。 情報理論の設定に焦点をあて、これらのスキームの構造とセキュリティにいくつかの制限を与えます。
  論文  参考訳（メタデータ） (2021-03-26T15:12:10Z)
• GreedyFool: Distortion-Aware Sparse Adversarial Attack [138.55076781355206]
  現代のディープニューラルネットワーク(DNN)は、敵のサンプルに対して脆弱である。 スパース逆数サンプルは、数ピクセルだけを摂動させることでターゲットモデルを騙すことができる。 GreedyFoolと呼ばれる2段階の歪みを考慮したグリーディ法を提案する。
  論文  参考訳（メタデータ） (2020-10-26T17:59:07Z)
• SMYRF: Efficient Attention using Asymmetric Clustering [103.47647577048782]
  本稿では,注目度を近似する新しいタイプのバランスクラスタリングアルゴリズムを提案する。 SMYRFは、再トレーニングすることなく、高密度の注意層をドロップインで置き換えることができる。 SMYRFは,訓練前後の集中的注意と相互に使用できることが示唆された。
  論文  参考訳（メタデータ） (2020-10-11T18:49:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。