論文の概要: Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions

• arxiv url: http://arxiv.org/abs/2410.00792v1
• Date: Tue, 1 Oct 2024 15:32:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-05 03:55:54.863287
• Title: Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions
• Title（参考訳）: サイクロトミック亜拡張の無限族に対する高速乗算とPLWE-RLWE等価性
• Authors: Joonas Ahola, Iván Blanco-Chacón, Wilmar Bolaños, Antti Haavikko, Camilla Hollanti, Rodrigo Martín Sánchez-Ledesma,
• Abstract要約: RLWE(Ring Learning With Errors)問題とPLWE(Polynomial Learning With Errors)問題との等価性を実証する。 また、最大実部分体の環内の2つの要素の積を計算するための高速整数についても述べる。
• 参考スコア（独自算出の注目度）: 6.487242614495099
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove the equivalence between the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems for the maximal totally real subfield of the $2^r 3^s$-th cyclotomic field for $r \geq 3$ and $s \geq 1$. Moreover, we describe a fast algorithm for computing the product of two elements in the ring of integers of these subfields. This multiplication algorithm has quasilinear complexity in the dimension of the field, as it makes use of the fast Discrete Cosine Transform (DCT). Our approach assumes that the two input polynomials are given in a basis of Chebyshev-like polynomials, in contrast to the customary power basis. To validate this assumption, we prove that the change of basis from the power basis to the Chebyshev-like basis can be computed with $\mathcal{O}(n \log n)$ arithmetic operations, where $n$ is the problem dimension. Finally, we provide a heuristic and theoretical comparison of the vulnerability to some attacks for the $p$-th cyclotomic field versus the maximal totally real subextension of the $4p$-th cyclotomic field for a reasonable set of parameters of cryptographic size.
• Abstract（参考訳）: RLWE(Ring Learning With Errors)とPLWE(Polynomial Learning With Errors)の2^r 3^s$-th cyclotomic field for $r \geq 3$ and $s \geq 1$。 さらに、これらの部分体の整数環における2つの要素の積を計算するための高速アルゴリズムについて述べる。 この乗算アルゴリズムは、高速離散コサイン変換(DCT)を利用するため、フィールドの次元において準線形複雑性を持つ。 我々のアプローチは、2つの入力多項式がチェビシェフ様多項式の基底で与えられると仮定する。 この仮定を検証するために、パワー基底からチェビシェフ基底への基底の変化を$\mathcal{O}(n \log n)$算術演算で計算できることを証明した。 最後に、暗号サイズの妥当なパラメータ集合に対して、この脆弱性を$p$-th cyclotomic field に対する攻撃に対して、最大で$4p$-th cyclotomic field の最大実数部分拡張に対してヒューリスティックかつ理論的に比較する。

関連論文リスト

• Parallel Quantum Signal Processing Via Polynomial Factorization [3.1981483719988235]
  量子並列信号処理アルゴリズムを開発した。 我々のアルゴリズムは、$texttr (P(rho)$ over $k$の計算を並列化し、クエリの深さを$d/k$に減らし、QSPの時間空間トレードオフのファミリを可能にする。 これにより、量子コンピュータに適した特性推定が可能となり、$O(textpoly(d) 2(k) )$ で測定数を増やすことで実現される。
  論文  参考訳（メタデータ） (2024-09-27T17:54:30Z)
• A Novel Finite Fractional Fourier Transform and its Quantum Circuit Implementation on Qudits [0.0]
  離散分数フーリエ変換(DFrFT)の新しい数論的定義を提案する。 DFrFT は算術回転群 $SO_2[mathbbZ_pn]$ の生成元の N 倍 N$ 次元ユニタリ表現として定義される。
  論文  参考訳（メタデータ） (2024-09-09T16:15:53Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors [1.249418440326334]
  二進体 $mathbbF$ 上の極大族を特徴づける。 我々の発見は、よりオープンないくつかの質問を呼び起こし、この研究の拡張バージョンで対処する予定です。
  論文  参考訳（メタデータ） (2024-05-14T16:30:28Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Using 1-Factorization from Graph Theory for Quantum Speedups on Clique Problems [0.0]
  完全グラフの一因子化に基づく新しい量子オラクル設計を提供する。 また、Triangle Findingの時間複雑性を$O(n2.25 poly(log n))$に下げる際の、これらのオラクルの1つの利用についても論じる。
  論文  参考訳（メタデータ） (2023-08-31T15:59:35Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。 巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。 我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
  論文  参考訳（メタデータ） (2023-01-04T04:15:40Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

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