論文の概要: Unconditional foundations for supersingular isogeny-based cryptography

• arxiv url: http://arxiv.org/abs/2502.17010v1
• Date: Mon, 24 Feb 2025 09:46:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:51:30.126789
• Title: Unconditional foundations for supersingular isogeny-based cryptography
• Title（参考訳）: 超特異等質暗号の無条件基礎
• Authors: Arthur Herlédan Le Merdy, Benjamin Wesolowski,
• Abstract要約: 我々は、超特異等質問題(等質性)が最悪の環問題(EndRing)と最大順序問題(MaxOrder)に等しいことを証明した。 暗号アプリケーションの場合、ランダムなインスタンスでは平均的に計算上の問題が難しい。 この結果を拡張して、上記の古典的問題のどれかが難しい場合、それらすべてが平均的に難しいことを証明する。
• 参考スコア（独自算出の注目度）: 5.01069065110753
• License:
• Abstract: In this paper, we prove that the supersingular isogeny problem (Isogeny), endomorphism ring problem (EndRing) and maximal order problem (MaxOrder) are equivalent under probabilistic polynomial time reductions, unconditionally.Isogeny-based cryptography is founded on the presumed hardness of these problems, and their interconnection is at the heart of the design and analysis of cryptosystems like the SQIsign digital signature scheme. Previously known reductions relied on unproven assumptions such as the generalized Riemann hypothesis. In this work, we present unconditional reductions, and extend this network of equivalences to the problem of computing the lattice of all isogenies between two supersingular elliptic curves (HomModule).For cryptographic applications, one requires computational problems to be hard on average for random instances. It is well-known that if Isogeny is hard (in the worst case), then it is hard for random instances. We extend this result by proving that if any of the above-mentionned classical problems is hard in the worst case, then all of them are hard on average. In particular, if there exist hard instances of Isogeny, then all of Isogeny, EndRing, MaxOrder and HomModule are hard on average.
• Abstract（参考訳）: 本稿では,超特異等質問題(アイソジニー),自己準同型リング問題(エンデジング),最大次数問題(MaxOrder)が確率多項式時間短縮の下で等価であることを証明する。 これまで知られていた還元は、一般化されたリーマン予想のような証明されていない仮定に依存していた。 本研究では,2つの超特異楕円曲線(HomModule)間のすべての等質格子の計算問題に同値ネットワークを拡張した。 暗号アプリケーションの場合、ランダムなインスタンスでは平均的に計算上の問題が難しい。 イソジェニーが(最悪の場合)困難であれば、ランダムなインスタンスにとって難しいことはよく知られている。 この結果は、上記の古典的問題のどれかが最悪の場合に難しい場合、それらすべてが平均的に難しいことを証明して拡張する。 特に、Isogenyのハードインスタンスが存在する場合、Isogeny、EndRing、MaxOrder、HomModuleの全ては平均的に難しい。

関連論文リスト

• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  MathGAPは、それらの算術的証明構造に関する仕様に従って、問題文と連鎖推論トレースを生成する。 MathGAP を用いて, LLM はより深く, より広くなるにつれて, 性能が著しく低下することがわかった。
  論文  参考訳（メタデータ） (2024-10-17T12:48:14Z)
• 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)
• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。 特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
  論文  参考訳（メタデータ） (2024-02-01T09:18:34Z)
• The supersingular Endomorphism Ring and One Endomorphism problems are equivalent [5.01069065110753]
  自己準同型環問題は、超特異楕円曲線間の任意の等元性を計算する問題と等価である。 我々は、追加情報を持つ等質グラフの研究のための柔軟なフレームワークを導入する。
  論文  参考訳（メタデータ） (2023-09-19T08:47:12Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Clique Homology is QMA1-hard [0.0]
  simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。 これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。 本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
  論文  参考訳（メタデータ） (2022-09-23T18:14:16Z)
• Failing to hash into supersingular isogeny graphs [4.57147786707036]
  重要な暗号オープン問題は、信頼できる権威なしで「ハード超特異曲線」の具体例を作成することである。 我々は、さらなる研究を刺激し、この取り組みの課題と障害に光を当てることを望んで、この問題を解決するために失敗した多くの試みを文書化しています。
  論文  参考訳（メタデータ） (2022-04-30T02:56:47Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
  我々は、$mathcal N=2 $ 超対称性を持つフェルミオンハミルトニアンの文脈における局所ハミルトニアン問題の複雑さを考える。 これを研究する主な動機は、超対称系の基底状態エネルギーがちょうどゼロであることと、あるコホモロジー群が非自明であることである。
  論文  参考訳（メタデータ） (2021-06-30T18:00:01Z)
• Causal Expectation-Maximisation [70.45873402967297]
  ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。 我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。 我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
  論文  参考訳（メタデータ） (2020-11-04T10:25:13Z)
• On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems [7.722592882475735]
  複素ベクトル $mathbfxin mathbbCn$ を $mangle A-imathbfx, mathbfxr_i=1m から復元する問題を考える。 一般に、NP-ハードが解ける二次問題であるだけでなく、実際には特定できないかもしれない。
  論文  参考訳（メタデータ） (2020-02-04T00:35:09Z)

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

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