論文の概要: Principal ideal problem and ideal shortest vector over rational primes in power-of-two cyclotomic fields

• arxiv url: http://arxiv.org/abs/2601.07511v1
• Date: Mon, 12 Jan 2026 13:09:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-13 19:08:01.39426
• Title: Principal ideal problem and ideal shortest vector over rational primes in power-of-two cyclotomic fields
• Title（参考訳）: 2つのシクロトミック場における主イデアル問題と有理素数上のイデアル最短ベクトル
• Authors: Gaohao Cui, Jianing Li, Jincheng Zhuang,
• Abstract要約: 理想格子上の最短ベクトル問題(SVP)は、リング-LWE問題と密接に関連している。 2つのシクロトミック場は、リング-LWEをインスタンス化するためにしばしば採用される。
• 参考スコア（独自算出の注目度）: 9.34954399532282
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The shortest vector problem (SVP) over ideal lattices is closely related to the Ring-LWE problem, which is widely used to build post-quantum cryptosystems. Power-of-two cyclotomic fields are frequently adopted to instantiate Ring-LWE. Pan et al. (EUROCRYPT~2021) explored the SVP over ideal lattices via the decomposition fields and, in particular determined the length of ideal lattices over rational primes $p\equiv3,5\pmod{8}$ in power-of-two cyclotomic fields via explicit construction of reduced lattice bases. In this work, we first provide a new method (different from analyzing lattice bases) to analyze the length of the shortest vector in prime ideals in $\mathbb{Z}[ζ_{2^{n+1}}]$ when $p\equiv3,5\pmod{8}$. Then we precisely characterize the length of the shortest vector on the cases of $p\equiv7,9\pmod{16}$. Furthermore, we derive a new upper bound for this length, which is tighter than the bound obtained from Minkowski's theorem. Our key technique is to investigate whether a generator of a principal ideal can achieve the shortest length after embedding as a vector. If this holds for the ideal, finding the shortest vector in this ideal can be reduced to finding its shortest generator.
• Abstract（参考訳）: 理想格子上の最短ベクトル問題(SVP)は、量子後暗号システムを構築するために広く用いられているリング-LWE問題と密接に関連している。 2つのシクロトミック場は、リング-LWEをインスタンス化するためにしばしば採用される。 Pan et al (EUROCRYPT~2021) は分解体を通して理想格子上のSVPを探索し、特に可算素数$p\equiv3,5\pmod{8}$のイデアル格子の長さを、還元された格子基底の明示的な構成を通じて2つのシクロトミック場において決定した。 この研究において、まず、$p\equiv3,5\pmod{8}$ のとき、素イデアルにおける最短ベクトルの長さを解析するための新しい方法(格子基底の解析とは異なる)を提案する。 すると、$p\equiv7,9\pmod{16}$の場合に最も短いベクトルの長さを正確に特徴づける。 さらに、ミンコフスキーの定理から得られる境界よりも厳密な、この長さの新しい上界を導出する。 本手法は,主イデアルの生成元がベクトルとして埋め込んだ後,最短長を達成できるかどうかを検討することである。 これがイデアルに対して成り立つなら、このイデアルの最も短いベクトルを見つけることは、最も短い生成元を見つけることに還元することができる。

関連論文リスト

• Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization [55.002497070656624]
  Broximal Point Method(BPM)は、現在の反復を中心にした標準球よりも目的関数を反復的に最小化する、理想的な最適化フレームワークを提供する。 顕著な大域収束保証、線形収束、および正規閉凸函数に対する有限のステップを享受する。 本稿では、BPMの収束理論が、このより一般的な非ユークリッド的な設定に拡張できるかどうかを問う。
  論文  参考訳（メタデータ） (2025-10-01T12:32:52Z)
• On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
  平面トーラスから構築したグラフ上での最大独立集合(MIS)問題として問題を再構成することにより、$m_1(mathbbR2)$を推定する新しいアプローチを導入する。 提案手法の理論的正当性によって支持された実験結果から, 十分に広い範囲のパラメータに対して, この手法が既知の下界を改善できないことを示す。
  論文  参考訳（メタデータ） (2024-11-20T12:07:19Z)
• Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices [19.216283072982005]
  スパースベクトルを見つけることは、コード、部分空間、格子を含むいくつかの文脈で生じる根本的な問題である。 我々は、PCP定理をバイパスする新しいアプローチを用いて、これらの変種すべてに対して強い不適合性を証明した。 我々の主な結果は、任意の定数係数内の実部分空間における最も広いベクトルを近似することがNPハードであることである。
  論文  参考訳（メタデータ） (2024-10-03T16:22:07Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension $k$ Codes [1.8416014644193066]
  共次元$k$ over $mathbbZ_Pd$, ここでは$P$は素数である。 共次元の$$は、プロジェクションのパッキング特性である mod $P$ を1つの双対符号ワードに初期セットの非格子ベクトルに利用することで解決される。 そこで本研究では,反復数,すなわち全長拡大係数を最小化して,短い格子ベクトルが得られることを示す。
  論文  参考訳（メタデータ） (2024-01-22T22:17:41Z)
• Embedding Integer Lattices as Ideals into Polynomial Rings [29.240943119083678]
  さらに、イデアル格子の付加構造を研究し、その係数を埋め込むことで、与えられたイデアル格子をイデアルとして無限に多くの異なる環に埋め込むことができる。 Ding と Lindner のアルゴリズムには、ある理想的な格子をそれらのアルゴリズムで特定できない欠陥がある。
  論文  参考訳（メタデータ） (2023-07-24T03:06:49Z)
• Subgroup-based Rank-1 Lattice Quasi-Monte Carlo [51.877197074344586]
  グループ理論に基づく単純な閉形式ランク1格子構築法を提案する。 本手法は,ベンチマーク統合テスト問題とカーネル近似問題において,優れた近似性能を実現する。
  論文  参考訳（メタデータ） (2020-10-29T03:42:30Z)

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

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