論文の概要: Learning with Errors over Group Rings Constructed by Semi-direct Product

• arxiv url: http://arxiv.org/abs/2311.15868v2
• Date: Fri, 1 Dec 2023 15:33:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 15:42:08.078171
• Title: Learning with Errors over Group Rings Constructed by Semi-direct Product
• Title（参考訳）: セミダイレクト製品によるグループリング上の誤り学習
• Authors: Jiaqi Liu, Fang-Wei Fu,
• Abstract要約: グループリング LWE (GR-LWE) はLearning with Errors (LWE) 問題の拡張である。 Ring-LWEの拡張として、GR-LWEは計算硬度を維持し、多くのシナリオに適用することができる。 GR-LWEサンプルはセマンティックにセキュアな公開鍵システムを構築するために利用することができる。
• 参考スコア（独自算出の注目度）: 26.148950348885972
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Learning with Errors (LWE) problem has been widely utilized as a foundation for numerous cryptographic tools over the years. In this study, we focus on an algebraic variant of the LWE problem called Group ring LWE (GR-LWE). We select group rings (or their direct summands) that underlie specific families of finite groups constructed by taking the semi-direct product of two cyclic groups. Unlike the Ring-LWE problem described in \cite{lyubashevsky2010ideal}, the multiplication operation in the group rings considered here is non-commutative. As an extension of Ring-LWE, it maintains computational hardness and can be potentially applied in many cryptographic scenarios. In this paper, we present two polynomial-time quantum reductions. Firstly, we provide a quantum reduction from the worst-case shortest independent vectors problem (SIVP) in ideal lattices with polynomial approximate factor to the search version of GR-LWE. This reduction requires that the underlying group ring possesses certain mild properties; Secondly, we present another quantum reduction for two types of group rings, where the worst-case SIVP problem is directly reduced to the (average-case) decision GR-LWE problem. The pseudorandomness of GR-LWE samples guaranteed by this reduction can be consequently leveraged to construct semantically secure public-key cryptosystems.
• Abstract（参考訳）: LWE問題(Learning with Errors)は、長年にわたり多くの暗号ツールの基礎として広く利用されてきた。 本研究では,群環 LWE (GR-LWE) と呼ばれるLWE問題の代数的変種に着目した。 2つの巡回群の半直積を取ることによって構成される有限群の特定の族を下敷きにする群環(あるいはそれらの直和環)を選択する。 \cite{lyubashevsky2010ideal} で述べられている Ring-LWE 問題とは異なり、ここで考慮される群環の乗法演算は非可換である。 Ring-LWEの拡張として、計算硬度を維持し、多くの暗号シナリオに適用できる可能性がある。 本稿では,2つの多項式時間量子還元法を提案する。 まず,最短の独立ベクトル問題 (SIVP) から GR-LWE の探索版への多項式近似係数を持つ理想格子への量子化を提案する。 第二に、最悪のSIVP問題は(平均ケース)決定GR-LWE問題に直接還元される。 この削減によって保証されるGR-LWEサンプルの擬似ランダム性は、セマンティックにセキュアな公開鍵暗号システムを構築するために利用することができる。

関連論文リスト

• A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More [1.1893324664457547]
  本稿では,古典的および量子的設定における暗号問題の解法における汎用的アプローチの限界について検討する。 両方のモデルにおいて、両方のモデルの量子的下界は、ある種の古典的な前処理を可能にする。
  論文  参考訳（メタデータ） (2024-02-17T13:00:47Z)
• Lattice attack on group ring NTRU: The case of the dihedral group [2.106410091047004]
  本稿では,NTRU型暗号システムの公開鍵に対する格子攻撃に対して,二面体群はより優れたセキュリティを保証していないことを示す。 二面体群に基づくGR-NTRUで生成された原格子の次元の半分の2つの格子でSVPを解くことで、秘密鍵の取得が可能であることを証明した。
  論文  参考訳（メタデータ） (2023-09-15T10:50:46Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• The dihedral hidden subgroup problem [0.0]
  有限群に対する標準部分群量子アルゴリズムの観点から、二面体群に対する隠れた問題の例を示す。 二面体コセット問題と量子状態のクローンとの新たな接続について説明する。
  論文  参考訳（メタデータ） (2021-06-18T04:19:10Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。 RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。 我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
  論文  参考訳（メタデータ） (2021-06-02T01:37:52Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-11T03:39:08Z)
• A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups [115.58550697886987]
  行列群の同変層を解くための完全一般的なアルゴリズムを提供する。 他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。 提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
  論文  参考訳（メタデータ） (2021-04-19T17:21:54Z)
• Robust subgroup discovery [0.2578242050187029]
  最小記述長原理を用いて最適ロバスト部分群発見の問題を定式化する。 RSDは、良いサブグループリストを見つけ、各イテレーションで最も重要なサブグループが追加されたことを保証します。 我々は,rsdが従来のサブグループ集合発見法を上回っている54のデータセットを,品質とサブグループリストサイズの観点から実証的に示す。
  論文  参考訳（メタデータ） (2021-03-25T09:04:13Z)
• GroupifyVAE: from Group-based Definition to VAE-based Unsupervised Representation Disentanglement [91.9003001845855]
  他の誘導バイアスを導入しないと、VAEベースの非監視的非絡み合いは実現できない。 グループ理論に基づく定義から導かれる制約を非確率的帰納的バイアスとして活用し,vaeに基づく教師なし不連続に対処する。 提案手法の有効性を検証するために,5つのデータセット上で,vaeベースモデルが最も目立つ1800モデルをトレーニングした。
  論文  参考訳（メタデータ） (2021-02-20T09:49:51Z)
• On construction of finite averaging sets for $SL(2, \mathbb{C})$ via its Cartan decomposition [0.0]
  リー群に対する物理量の平均化は、量子情報科学や量子光学など多くの文脈に現れる。 本研究では、一般の非コンパクト行列リー群上の平均化に対する有限平均化集合を構成する問題について検討する。 我々は、SL(2, mathbbC)$ に対してそのような集合を明示的に計算するが、この構成は他の場合にも適用できる。
  論文  参考訳（メタデータ） (2020-10-29T17:26:33Z)
• A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz [68.8204255655161]
  本稿では,変分量子固有解法(VQE)アルゴリズムのコンパイル戦略について述べる。 我々は、回路深さとゲート数を減らすために、ユニタリ結合クラスタ(UCC)アンサッツを使用する。
  論文  参考訳（メタデータ） (2020-07-20T22:26:16Z)

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

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