Fugu-MT 論文翻訳(概要): A New Algebraic Algorithm for LWE

論文の概要: A New Algebraic Algorithm for LWE

arxiv url: http://arxiv.org/abs/2608.29977v1
Date: Sun, 30 Aug 2026 19:09:53 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-01 18:31:31.138362
Title: A New Algebraic Algorithm for LWE
Title（参考訳）: LWEのための新しい代数アルゴリズム
Abstract要約: LWE(Learning With Errors)問題は、現代の暗号とポスト量子セキュリティの中心である。本研究では,探索-LWE問題に対する新しい代数的アルゴリズムを提案する。高いレベルでは、アルゴリズムは線形代数的手法とGroebnerに基づくS-polynomialベースの手法を組み合わせる。
参考スコア（独自算出の注目度）: 2.1824288041476008
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: The Learning With Errors (LWE) problem, introduced by Regev in 2005, is central to modern cryptography and post-quantum security. The algorithms to solve the search version of the problem, Search-LWE, can be broadly categorised into algebraic, combinatorial and lattice-based. In this work we propose a new algebraic algorithm for the Search-LWE problem. At a high level, the algorithm combines linear-algebraic techniques with S-polynomial-based methods from Groebner basis computation. We provide a direct complexity analysis of our algorithm, avoiding semi-regularity assumptions and complexity bounds derived from the degree of regularity. Our algorithm achieves a polynomial improvement in complexity over prior results that use Groebner basis methods to solve Search-LWE.
Abstract（参考訳）: 2005年にRegevによって導入されたLearning With Errors(LWE)問題は、現代の暗号とポスト量子セキュリティの中心である。この問題の探索版である Search-LWE を解くアルゴリズムは、代数的、組合せ的、格子的に大別できる。本研究では,探索-LWE問題に対する新しい代数的アルゴリズムを提案する。高いレベルでは、このアルゴリズムは線形代数的手法とGroebner基底計算のS-ポリノミカル法を組み合わせたものである。半正則性の仮定や、正規性の次数から導かれる複雑性境界を回避し、アルゴリズムの直接的複雑性解析を行う。提案アルゴリズムは,Groebner 基底法を用いて検索-LWE を解く先行結果よりも複雑な多項式を解く。

関連論文リスト

A Robust Algorithm for Non-IID Machine Learning Problems with Convergence Analysis [2.4462606119036456]
本研究では,非滑らかな最適化,二次計画法,反復過程に基づく最小値問題の解法を改良した数値アルゴリズムを提案する。このようなアルゴリズムは、ロバスト最適化や不均衡学習など、様々な分野に広く適用することができる。
論文参考訳（メタデータ） (2025-07-01T14:41:59Z)
A New Algorithm for Computing Branch Number of Non-Singular Matrices over Finite Fields [1.3332839594069594]
状態差やリニアマスクにおけるゼロでない要素の数は、アクティブなSボックスと直接相関する。微分分岐数または線形分岐数は、SPN暗号の2つの連続するラウンドにおける活性S-ボックスの最小数を示す。本稿では,有限体上の非特異行列の分岐数を計算するための新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-05-11T13:06:03Z)
The Complexity of Algebraic Algorithms for LWE [0.0]
我々は、LWEシステム上でのGr"オブナー基底計算の複雑さを研究するために、Arora-Geモデルを再検討する。我々は、Semaev & TentiのGr"obner基底アルゴリズムを有限の正則性を持つ任意の系に一般化する。
論文参考訳（メタデータ） (2024-02-12T17:59:26Z)
Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approach [12.679411410749521]
本稿では,ニューラルネットワークによる格子縮小問題に対するアルゴリズム空間のパラメータ化と,教師付きデータを持たないアルゴリズムの探索を行うことが可能であることを示す。本研究では,一様行列の因子を出力する深層ニューラルネットワークを設計し,非直交格子基底をペナルライズして自己指導的に学習する。提案手法は,一連のベンチマークにおいて,Lenstra-Lenstra-Lov'aszアルゴリズムに匹敵する複雑性と性能を持つアルゴリズムが得られることを示す。
論文参考訳（メタデータ） (2023-11-14T13:54:35Z)
Polynomial-time Solver of Tridiagonal QUBO, QUDO and Tensor QUDO problems with Tensor Networks [41.94295877935867]
本稿では,三対角四角形非制約二元最適化問題の解法として量子インスピレーション付きテンソルネットワークアルゴリズムを提案する。また、直列鎖内の一方の隣り合う相互作用を伴うより一般的な2次非制約離散最適化問題を解く。
論文参考訳（メタデータ） (2023-09-19T10:45:15Z)
Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文参考訳（メタデータ） (2023-02-24T18:41:48Z)
First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文参考訳（メタデータ） (2022-04-07T00:11:05Z)
Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
論文参考訳（メタデータ） (2021-05-18T05:23:53Z)
Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
ガウスの下の半空間を不可知的に学習する問題を考察する。我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
論文参考訳（メタデータ） (2021-02-10T18:40:44Z)
Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-15T13:40:07Z)
Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文参考訳（メタデータ） (2020-02-21T17:45:32Z)

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