論文の概要: On the Classical Hardness of the Semidirect Discrete Logarithm Problem in Finite Groups
- arxiv url: http://arxiv.org/abs/2508.05048v1
- Date: Thu, 07 Aug 2025 05:59:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-08 18:59:39.720587
- Title: On the Classical Hardness of the Semidirect Discrete Logarithm Problem in Finite Groups
- Title（参考訳）: 有限群における半直接離散対数問題の古典的硬さについて
- Authors: Mohammad Ferry Husnil Arif, Muhammad Imran,
- Abstract要約: 量子後暗号プロトコルの基礎として,有限群の半間接離散対数問題 (SDLP) が提案された。
近年の研究では、有限群のSDLPは効率的な量子アルゴリズムを認め、量子抵抗を損なうことが示されている。
- 参考スコア（独自算出の注目度）: 2.4631262987844247
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The semidirect discrete logarithm problem (SDLP) in finite groups was proposed as a foundation for post-quantum cryptographic protocols, based on the belief that its non-abelian structure would resist quantum attacks. However, recent results have shown that SDLP in finite groups admits efficient quantum algorithms, undermining its quantum resistance. This raises a fundamental question: does the SDLP offer any computational advantages over the standard discrete logarithm problem (DLP) against classical adversaries? In this work, we investigate the classical hardness of SDLP across different finite group platforms. We establish that the group-case SDLP can be reformulated as a generalized discrete logarithm problem, enabling adaptation of classical algorithms to study its complexity. We present a concrete adaptation of the Baby-Step Giant-Step algorithm for SDLP, achieving time and space complexity $O(\sqrt{r})$ where $r$ is the period of the underlying cycle structure. Through theoretical analysis and experimental validation in SageMath, we demonstrate that the classical hardness of SDLP is highly platform-dependent and does not uniformly exceed that of standard DLP. In finite fields $\mathbb{F}_p^*$, both problems exhibit comparable complexity. Surprisingly, in elliptic curves $E(\mathbb{F}_p)$, the SDLP becomes trivial due to the bounded automorphism group, while in elementary abelian groups $\mathbb{F}_p^n$, the SDLP can be harder than DLP, with complexity varying based on the eigenvalue structure of the automorphism. Our findings reveal that the non-abelian structure of semidirect products does not inherently guarantee increased classical hardness, suggesting that the search for classically hard problems for cryptographic applications requires more careful consideration of the underlying algebraic structures.
- Abstract（参考訳）: 有限群における半間接離散対数問題(SDLP)は、その非アーベル構造が量子攻撃に抵抗するという考えに基づいて、後量子暗号プロトコルの基礎として提案された。
しかし、最近の研究では、有限群のSDLPは効率的な量子アルゴリズムを認め、量子抵抗を損なうことが示されている。
SDLPは、古典的な敵に対する標準的な離散対数問題(DLP)に対して、何らかの計算上の優位性を提供しますか?
本研究では,異なる有限群プラットフォーム間のSDLPの古典的硬さについて検討する。
グループケース SDLP は一般化された離散対数問題として再構成可能であることを確認し、古典的アルゴリズムの適応による複雑性の研究を可能にする。
SDLPのためのBaby-Step Giant-Stepアルゴリズムを具体化して、時間と空間の複雑さを$O(\sqrt{r})$とする。
SageMath の理論的解析と実験的検証により,SDLP の古典的硬さは高プラットフォーム依存であり,標準 DLP よりも一様ではないことを示した。
有限体 $\mathbb{F}_p^*$ では、どちらの問題も同等の複雑性を示す。
驚いたことに、楕円曲線 $E(\mathbb{F}_p)$ において、SDLP は有界自己同型群により自明となり、一方、基本アーベル群 $\mathbb{F}_p^n$ では、SDLP は DLP よりも難しくなり、自己同型の固有値構造によって複雑さが変化する。
この結果から, 半直積の非アーベル構造は, 古典的硬さの増大を本質的に保証しないことが明らかとなり, 古典的難解問題の探索には, 基礎となる代数的構造をより慎重に検討する必要があることが示唆された。
関連論文リスト
- Simulation of Shor algorithm for discrete logarithm problems with comprehensive pairs of modulo p and order q [0.0]
量子回路をシミュレートし、モジュロ$pの一般的なペアで動作させ、$qをオーダーする。
p$ が等しければ、セーフプライム群とシュノール群の強みがどの程度同じかを示す。
特に、加算回路で搬送器を用いる場合、ショアのアルゴリズムの下では$p=$48$ビットのシュノーラー群の暗号強度は$p=$48$ビットの安全プリム群のそれとほぼ同値であることが実験的に理論的に示された。
論文 参考訳（メタデータ） (2025-03-31T10:39:10Z) - Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。
逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。
これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum
Factoring, and More [1.1893324664457547]
本稿では,古典的および量子的設定における暗号問題の解法における汎用的アプローチの限界について検討する。
両方のモデルにおいて、両方のモデルの量子的下界は、ある種の古典的な前処理を可能にする。
論文 参考訳（メタデータ） (2024-02-17T13:00:47Z) - Efficient quantum algorithms for some instances of the semidirect
discrete logarithm problem [2.90985742774369]
SDLPは,いくつかの重要な症例においてさらに容易であることを示す。
SDLPのハードネスを前提としたセキュリティ仮定を前提としたSPDH-Signと類似の暗号系が量子攻撃に対して安全でないことを示す。
論文 参考訳（メタデータ） (2023-12-21T16:58:59Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem [0.8947831206263182]
グループベースの暗号は、量子後暗号における比較的未発見の家系である。
いわゆる半間接離散対数問題(Semidirect Discrete Logarithm Problem, SDLP)は、その最も中心的な問題の一つである。
SDLPのセキュリティ分析を初めて行った。
論文 参考訳（メタデータ） (2022-09-06T20:50:17Z) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳（メタデータ） (2022-06-02T15:21:55Z) - An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor [2.3351527694849574]
整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。
量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。
この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
論文 参考訳（メタデータ） (2022-01-31T18:58:33Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - The Complexity of Adversarially Robust Proper Learning of Halfspaces
with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。
この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文 参考訳（メタデータ） (2020-07-30T04:18:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。