論文の概要: Efficient quantum algorithms for some instances of the semidirect
discrete logarithm problem
- arxiv url: http://arxiv.org/abs/2312.14028v1
- Date: Thu, 21 Dec 2023 16:58:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-22 13:51:59.923233
- Title: Efficient quantum algorithms for some instances of the semidirect
discrete logarithm problem
- Title（参考訳）: 半間接離散対数問題に対する効率的な量子アルゴリズム
- Authors: Muhammad Imran and G\'abor Ivanyos
- Abstract要約: SDLPは,いくつかの重要な症例においてさらに容易であることを示す。
SDLPのハードネスを前提としたセキュリティ仮定を前提としたSPDH-Signと類似の暗号系が量子攻撃に対して安全でないことを示す。
- 参考スコア（独自算出の注目度）: 2.90985742774369
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The semidirect discrete logarithm problem (SDLP) is the following analogue of
the standard discrete logarithm problem in the semidirect product semigroup
$G\rtimes \mathrm{End}(G)$ for a finite semigroup $G$. Given $g\in G, \sigma\in
\mathrm{End}(G)$, and $h=\prod_{i=0}^{t-1}\sigma^i(g)$ for some integer $t$,
the SDLP$(G,\sigma)$, for $g$ and $h$, asks to determine $t$. As Shor's
algorithm crucially depends on commutativity, it is believed not to be
applicable to the SDLP. Previously, the best known algorithm for the SDLP was
based on Kuperberg's subexponential time quantum algorithm. Still, the problem
plays a central role in the security of certain proposed cryptosystems in the
family of \textit{semidirect product key exchange}. This includes a recently
proposed signature protocol called SPDH-Sign. In this paper, we show that the
SDLP is even easier in some important special cases. Specifically, for a finite
group $G$, we describe quantum algorithms for the SDLP in $G\rtimes
\mathrm{Aut}(G)$ for the following two classes of instances: the first one is
when $G$ is solvable and the second is when $G$ is a matrix group and a power
of $\sigma$ with a polynomially small exponent is an inner automorphism of $G$.
We further extend the results to groups composed of factors from these classes.
A consequence is that SPDH-Sign and similar cryptosystems whose security
assumption is based on the presumed hardness of the SDLP in the cases described
above are insecure against quantum attacks. The quantum ingredients we rely on
are not new: these are Shor's factoring and discrete logarithm algorithms and
well-known generalizations.
- Abstract（参考訳）: 半直離散対数問題(semidirect discrete logarithm problem、sdlp)は、有限半群 $g$ に対する半直積半群 $g\rtimes \mathrm{end}(g)$ における標準離散対数問題の例である。
g\in g, \sigma\in \mathrm{end}(g)$, and $h=\prod_{i=0}^{t-1}\sigma^i(g)$ が与えられたとき、sdlp$(g,\sigma)$ は$g$ と $h$ に対して、$t$ を決定する。
Shorのアルゴリズムは可換性に依存するため、SDLPには適用できないと考えられている。
以前は、SDLPの最もよく知られたアルゴリズムは、クパーバーグの指数時間量子アルゴリズムに基づいていた。
しかし、この問題は \textit{semidirect product key exchange} の族において、提案された暗号システムのセキュリティにおいて中心的な役割を果たす。
これにはSPDH-Signと呼ばれる最近提案された署名プロトコルが含まれている。
本稿では,SDLPが重要な特殊ケースにおいてさらに容易であることを示す。
具体的には、有限群$G$に対して、次の2つのインスタンスのクラスに対して$G\rtimes \mathrm{Aut}(G)$でSDLPの量子アルゴリズムを記述する: 1つは、$G$が可解であるとき、2つ目は、$G$が行列群であり、多項式的に小さい指数を持つ$\sigma$が$G$の内部自己同型であるときである。
これらのクラスから得られた因子からなる群にさらに結果を拡張する。
その結果、上述のケースにおけるsdlpのハードネス推定に基づくセキュリティ仮定が量子攻撃に対して安全でないspdh符号および類似暗号システムが存在する。
私たちが依存する量子成分は新しいものではなく、shorのファクタリングと離散対数アルゴリズムとよく知られた一般化である。
関連論文リスト
- Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - Weak Schur sampling with logarithmic quantum memory [0.0]
弱いシュアサンプリングのための新しいアルゴリズムを提案する。
我々のアルゴリズムは、既約表現をインデックスするヤングラベルと対称群の多重度ラベルの両方を効率的に決定する。
論文 参考訳（メタデータ） (2023-09-21T10:02:46Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。
このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。
Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
論文 参考訳（メタデータ） (2023-07-06T15:32:50Z) - Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the
Cryptanalysis of pSIDH [5.398058794903461]
自己同型環問題(英語版)(IsERP)は、超特異曲線の間の同型写像の余領域の自己同型環を計算することを要求する。
次数が奇数で、多くの素因子が$O(loglog p)=$である等質性に対して、IsERPを解くための新しい量子時間アルゴリズムを導入する。
論文 参考訳（メタデータ） (2023-05-31T14:30:32Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU
Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。
正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文 参考訳（メタデータ） (2020-06-22T17:53:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。