論文の概要: The Complexity of Algebraic Algorithms for LWE

• arxiv url: http://arxiv.org/abs/2402.07852v2
• Date: Mon, 26 Feb 2024 12:10:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 07:28:31.141913
• Title: The Complexity of Algebraic Algorithms for LWE
• Title（参考訳）: LWEのための代数アルゴリズムの複雑さ
• Authors: Matthias Johann Steiner,
• Abstract要約: 我々は、LWEシステム上でのGr"オブナー基底計算の複雑さを研究するために、Arora-Geモデルを再検討する。 我々は、Semaev & TentiのGr"obner基底アルゴリズムを有限の正則性を持つ任意の系に一般化する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Arora & Ge introduced a noise-free polynomial system to compute the secret of a Learning With Errors (LWE) instance via linearization. Albrecht et al. later utilized the Arora-Ge polynomial model to study the complexity of Gr\"obner basis computations on LWE polynomial systems under the assumption of semi-regularity. In this paper we revisit the Arora-Ge polynomial and prove that it satisfies a genericity condition recently introduced by Caminata & Gorla, called being in generic coordinates. For polynomial systems in generic coordinates one can always estimate the complexity of DRL Gr\"obner basis computations in terms of the Castelnuovo-Mumford regularity and henceforth also via the Macaulay bound. Moreover, we generalize the Gr\"obner basis algorithm of Semaev & Tenti to arbitrary polynomial systems with a finite degree of regularity. In particular, existence of this algorithm yields another approach to estimate the complexity of DRL Gr\"obner basis computations in terms of the degree of regularity. In practice, the degree of regularity of LWE polynomial systems is not known, though one can always estimate the lowest achievable degree of regularity. Consequently, from a designer's worst case perspective this approach yields sub-exponential complexity estimates for general, binary secret and binary error LWE. In recent works by Dachman-Soled et al. the hardness of LWE in the presence of side information was analyzed. Utilizing their framework we discuss how hints can be incorporated into LWE polynomial systems and how they affect the complexity of Gr\"obner basis computations.
• Abstract（参考訳）: Arora & GeはLearning With Errors(LWE)インスタンスの秘密を線形化することで計算するノイズフリー多項式システムを導入した。 アルブレヒトらは後に、半正則性の仮定の下で、LWE多項式系のGr\"オブナー基底計算の複雑さを研究するために、Arora-Ge多項式モデルを利用した。 本稿ではArora-Ge多項式を再検討し、最近Caminata & Gorlaによって導入された一般性条件を満たすことを証明する。 一般座標における多項式系に対しては、常にカメルヌオボ・マンフォード正則性の観点からDRL Gr\"オブナー基底計算の複雑さを推定することができる。 さらに、Semaev & TentiのGr\"obner基底アルゴリズムを有限の正則性を持つ任意の多項式系に一般化する。 特に、このアルゴリズムの存在は、正規性の度合いの観点からDRL Gr\"オブナー基底計算の複雑さを推定する別のアプローチをもたらす。 実際には、LWE多項式系の正則性の度合いは知られていないが、常に最も低い到達可能な正則性の度合いを推定できる。 その結果、デザイナの最悪の場合から、このアプローチは一般、バイナリシークレット、バイナリエラーLWEの指数未満の複雑さの見積を導き出す。 Dachman-Soledらによる最近の研究で、サイド情報の存在下でのLWEの硬さについて分析した。 それらのフレームワークを利用することで、LWE多項式システムにヒントを組み込む方法や、Gr\"オブザーバ基底計算の複雑さにどのように影響するかについて議論する。

関連論文リスト

• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
  ユークリッド空間における集合の被覆数について上限を証明する。 ここでは、イムディン・コントによる最もよく知られた一般境界が改善されることが示される。 本稿では,3つの計算応用における結果のパワーについて説明する。
  論文  参考訳（メタデータ） (2023-11-09T03:06:59Z)
• Solving Degree Bounds For Iterated Polynomial Systems [0.0]
  我々は,MIMC,Feistel-MiMC,Feistel-MiMC-Hash,Hades,GMiMCに対する攻撃に対する正則性評価を行った。 我々の境界は、これらの設計に対するGr"オブナーベースアタックの仮定された複雑さと一致している。
  論文  参考訳（メタデータ） (2023-10-05T16:10:14Z)
• Automatic Solver Generator for Systems of Laurent Polynomial Equations [1.7188280334580197]
  同じ単項構造であるが様々な係数を持つ三角系(ローラン系)が与えられたとき、任意の族に対する解をできるだけ早く計算する解法を見つける。 ローラン方程式系に対する自動解法生成器を提案する。
  論文  参考訳（メタデータ） (2023-07-01T12:12:52Z)
• Blow-up Algorithm for Sum-of-Products Polynomials and Real Log Canonical Thresholds [0.0]
  紙は平均誤差関数を比較的単純な対数標準しきい値(RLCT)に置き換える RLCTは、ブローアップと呼ばれる操作によって特異性を解き放つことで得られる。 本稿では、積和(sop)と呼ばれる反復の爆破アルゴリズムについて考察する。
  論文  参考訳（メタデータ） (2023-03-21T06:40:06Z)
• Krylov complexity and orthogonal polynomials [30.445201832698192]
  クリロフ複雑性(Krylov complexity)は、ハイゼンベルク時間発展に適応した基底に関して作用素の成長を測定する。 この基底の構成はランツォの帰納法に依存している。
  論文  参考訳（メタデータ） (2022-05-25T14:40:54Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。 このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。 我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
  論文  参考訳（メタデータ） (2021-03-19T16:34:20Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

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