論文の概要: 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サンプルの擬似ランダム性は、セマンティックにセキュアな公開鍵暗号システムを構築するために利用することができる。
関連論文リスト
- VLWE: Variety-based Learning with Errors for Vector Encryption through Algebraic Geometry [1.3824176915623292]
格子ベースの暗号はポスト量子セキュリティの基礎である。
この研究は代数幾何学に基づく新しい構造格子問題であるバラエティ-LWE(VLWE)を導入する。
VLWEのセキュリティは、複数の独立したインスタンスに分散し、古典的および量子的攻撃に対するレジリエンスを示すことによって証明する。
論文 参考訳（メタデータ） (2025-02-11T06:04:24Z) - A parameter study for LLL and BKZ with application to shortest vector problems [0.20971479389679337]
与えられたSVPを単純化するために使用できる2つのよく知られたアルゴリズムは、Lenstra-Lenstra-Lov'asz (LLL)アルゴリズムとBlock Korkine-Zolotarev (BKZ)アルゴリズムである。
異なるサイズとモジュラリングを持つSVPに対する両アルゴリズムの性能について検討する。
論文 参考訳（メタデータ） (2025-02-07T18:41:44Z) - Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。
理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
論文 参考訳（メタデータ） (2024-11-29T05:29: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) - Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。
IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。