論文の概要: A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective

• arxiv url: http://arxiv.org/abs/2512.02087v1
• Date: Mon, 01 Dec 2025 12:48:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-03 21:04:45.562218
• Title: A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective
• Title（参考訳）: 数学的・暗号学的観点からの隠れ部分群問題に関する調査
• Authors: Simone Dutto, Pietro Mercuri, Nadir Murru, Lorenzo Romano,
• Abstract要約: 隠れサブグループ問題(HSP)は、公開鍵暗号システムのセキュリティ研究において重要な役割を果たす。 はじめに、北エフのアルゴリズムが HSP に対して効率的な量子解をもたらすアーベルの場合について概説する。 次に、一般効率のよい量子解が知られていない非アーベル HSP に関する技術の現状について検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide a survey on the Hidden Subgroup Problem (HSP), which plays an important role in studying the security of public-key cryptosystems. We first review the abelian case, where Kitaev's algorithm yields an efficient quantum solution to the HSP, recalling how classical problems (such as order finding, integer factorization, and discrete logarithm) can be formulated as abelian HSP instances. We then examine the current state of the art for non-abelian HSP, where no general efficient quantum solution is known, focusing on some relevant groups including dihedral group (connected to the shortest vector problem), symmetric groups (connected to the graph isomorphism problem), and semidirect product constructions (connected, in a special case, to the code equivalence problem). We also describe the main techniques for addressing the HSP in non-abelian cases, namely Fourier sampling and the black-box approach. Throughout the paper, we highlight the mathematical notions required and exploited in this context, providing a cryptography-oriented perspective.
• Abstract（参考訳）: 我々は、公開鍵暗号システムのセキュリティ研究において重要な役割を果たす隠れサブグループ問題(HSP)について調査する。 我々はまず、北エフのアルゴリズムがHSPに効率的な量子解をもたらすアーベルのケースをレビューし、古典的な問題(順序探索、整数分解、離散対数等)をアーベル HSP インスタンスとして定式化する方法を思い出した。 次に、二面体群(最短ベクトル問題に連結する)、対称群(グラフ同型問題に連結する)、半直積構成(特別の場合、コード同値問題に連結する)など、いくつかの関連する群に焦点を当て、一般効率な量子解が知られていない非アーベル HSP の現状について検討する。 また,非アーベルケース,すなわちフーリエサンプリングとブラックボックスアプローチにおいて,HSPに対処する主要な手法についても述べる。 論文全体を通して、この文脈で必要とされ、活用される数学的概念を強調し、暗号指向の視点を提供する。

関連論文リスト

• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  チュートリアルは変分量子回路とQUBO問題の概要から始まる。 次に、ハミルトンの定式化、ゲート分解、サンプル応用など、QAOAの詳細を探索する。 このチュートリアルはこれらの概念を高階ハミルトニアンに拡張し、関連する対称性と回路構成について議論する。
  論文  参考訳（メタデータ） (2025-11-23T09:54:20Z)
• Learning T-conjugated stabilizers: The multiple-squares dihedral StateHSP [0.25956507689419356]
  非アーベル状態HSPを位数8$の2進群のコピー(正方形の対称性)で解くアルゴリズムを提案する。 このアルゴリズムは、非パウリ安定化器、およびハミルトン分光の問題に関連する関連する対称性を学ぶことに興味がある。
  論文  参考訳（メタデータ） (2025-10-09T07:23:53Z)
• On the privacy of federated Clustering: A Cryptographic View [2.209921757303168]
  多くのプライバシ保存クラスタリングアルゴリズムは、完全なプライバシを保証するために、ホモモルフィック暗号化やセキュアなマルチパーティ計算のような暗号化技術を活用する。 本稿では,この複雑なトレードオフを考察し,反復アルゴリズムにおける連続暗号の必要性を疑問視する。 既存の格子型HSSP攻撃は,中間セントロイドの知識からプライベートデータの再構成に失敗していることを示す。
  論文  参考訳（メタデータ） (2023-12-13T09:04:14Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。 VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
  論文  参考訳（メタデータ） (2022-05-07T03:15:15Z)
• Polynomial-time quantum algorithm for solving the hidden subgroup problem [0.0]
  隠れ部分群問題(HSP)は量子計算における最も重要な問題の一つである。 我々は,HSPを,マルチステップ量子アルゴリズムによる量子アルゴリズムを用いて効率よく解けるネスト型構造化探索問題に還元できることを見出した。
  論文  参考訳（メタデータ） (2022-04-07T08:50:50Z)
• The Hidden Subgroup Problem for Universal Algebras [0.7832189413179361]
  隠れ部分群問題(英: Hidden Subgroup Problem、HSP)は、特殊の場合の整数分解、離散離散問題、グラフ同型、最短ベクトル問題を含む計算問題である。
  論文  参考訳（メタデータ） (2020-01-30T13:09:35Z)

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

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