論文の概要: Embedding Integer Lattices as Ideals into Polynomial Rings
- arxiv url: http://arxiv.org/abs/2307.12497v2
- Date: Tue, 20 Feb 2024 07:08:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-25 23:29:06.838828
- Title: Embedding Integer Lattices as Ideals into Polynomial Rings
- Title（参考訳）: 整数格子をポリノミアルリングに組み込む
- Authors: Yihang Cheng, Yansong Feng, Yanbin Pan,
- Abstract要約: さらに、イデアル格子の付加構造を研究し、その係数を埋め込むことで、与えられたイデアル格子をイデアルとして無限に多くの異なる環に埋め込むことができる。
Ding と Lindner のアルゴリズムには、ある理想的な格子をそれらのアルゴリズムで特定できない欠陥がある。
- 参考スコア（独自算出の注目度）: 29.240943119083678
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many lattice-based crypstosystems employ ideal lattices for high efficiency. However, the additional algebraic structure of ideal lattices usually makes us worry about the security, and it is widely believed that the algebraic structure will help us solve the hard problems in ideal lattices more efficiently. In this paper, we study the additional algebraic structure of ideal lattices further and find that a given ideal lattice in a polynomial ring can be embedded as an ideal into infinitely many different polynomial rings by the coefficient embedding. We design an algorithm to verify whether a given full-rank lattice in $\mathbb{Z}^n$ is an ideal lattice and output all the polynomial rings that the given lattice can be embedded into as an ideal with time complexity $\mathcal{O}(n^3B(B+\log n)$, where $n$ is the dimension of the lattice and $B$ is the upper bound of the bit length of the entries of the input lattice basis. We would like to point out that Ding and Lindner proposed an algorithm for identifying ideal lattices and outputting a single polynomial ring that the input lattice can be embedded into with time complexity $\mathcal{O}(n^5B^2)$ in 2007. However, we find a flaw in Ding and Lindner's algorithm that causes some ideal lattices can't be identified by their algorithm.
- Abstract（参考訳）: 多くの格子ベースのクリプトシステムは、高効率に理想的な格子を用いる。
しかし、イデアル格子の付加的な代数構造は、通常、セキュリティを心配するものであり、代数構造はイデアル格子の難しい問題をより効率的に解くのに役立つと広く信じられている。
本稿では、イデアル格子の代数構造をさらに研究し、多項式環の与えられたイデアル格子を係数埋め込みにより、イデアルとして無限に多くの異なる多項式環に埋め込むことができることを示す。
我々は、$\mathbb{Z}^n$ の与えられたフルランク格子が理想的な格子であるかどうかを検証するアルゴリズムを設計し、与えられた格子が時間複雑性を持つイデアルとして埋め込むことができるすべての多項式環を出力する。
Ding と Lindner は、理想的な格子を識別し、入力格子を時間複雑性$\mathcal{O}(n^5B^2)$で埋め込むことのできる単一の多項式環を出力するアルゴリズムを2007年に提案したことを指摘したい。
しかし、Ding と Lindner のアルゴリズムには、ある理想的な格子をそれらのアルゴリズムで特定できない欠陥がある。
関連論文リスト
- Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions [6.487242614495099]
RLWE(Ring Learning With Errors)問題とPLWE(Polynomial Learning With Errors)問題との等価性を実証する。
また、最大実部分体の環内の2つの要素の積を計算するための高速整数についても述べる。
論文 参考訳（メタデータ） (2024-10-01T15:32:02Z) - Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach [3.0079490585515343]
サブセット Sum 問題にモジュラー算術的アプローチを導入する。
本研究では,LLL削減基底ベクトルの長さを解析することにより,密度保証を向上できることを示す。
論文 参考訳（メタデータ） (2024-08-28T19:32:14Z) - Post-quantum encryption algorithms of high-degree 3-variable polynomial congruences: BS cryptosystems and BS key generation [0.0]
本稿では,3変数のBeal-Schurコングルースに基づく量子後暗号アルゴリズムを構築する。
この結果を用いて、単純でセキュアな量子後暗号アルゴリズムを生成する。
論文 参考訳（メタデータ） (2024-08-14T14:19:46Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Conditional Gradients for the Approximately Vanishing Ideal [0.0]
条件付き条件勾配の約消去理想アルゴリズム(CGAVI)
約イデアルのジェネレータの集合を構成するための条件条件勾配(CGAVI)について述べる。
構築されたジェネレータのセットは、データの構造をキャプチャし、教師付き学習のための線形分類器と組み合わせて使用できる特徴マップを生成する。
論文 参考訳（メタデータ） (2022-02-07T16:48:49Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳（メタデータ） (2020-10-13T17:26:09Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z) - Efficient quantum processing of ideals in finite rings [1.1724565818034947]
ポリ(log |R|)時間において、I に対して加法基底表現を求める方法を示す。
このアルゴリズムは、量子コンピュータが有限環に関する様々な問題を迅速に解くことができる有用なプリミティブであることを示す。
論文 参考訳（メタデータ） (2009-07-31T23:00:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。