論文の概要: The supersingular Endomorphism Ring and One Endomorphism problems are equivalent

• arxiv url: http://arxiv.org/abs/2309.10432v2
• Date: Mon, 16 Oct 2023 11:06:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 04:20:31.633038
• Title: The supersingular Endomorphism Ring and One Endomorphism problems are equivalent
• Title（参考訳）: 超特異同型環 Ring と 1 の同型問題は同値である
• Authors: Aurel Page, Benjamin Wesolowski,
• Abstract要約: 自己準同型環問題は、超特異楕円曲線間の任意の等元性を計算する問題と等価である。 我々は、追加情報を持つ等質グラフの研究のための柔軟なフレームワークを導入する。
• 参考スコア（独自算出の注目度）: 5.01069065110753
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The supersingular Endomorphism Ring problem is the following: given a supersingular elliptic curve, compute all of its endomorphisms. The presumed hardness of this problem is foundational for isogeny-based cryptography. The One Endomorphism problem only asks to find a single non-scalar endomorphism. We prove that these two problems are equivalent, under probabilistic polynomial time reductions. We prove a number of consequences. First, assuming the hardness of the endomorphism ring problem, the Charles--Goren--Lauter hash function is collision resistant, and the SQIsign identification protocol is sound. Second, the endomorphism ring problem is equivalent to the problem of computing arbitrary isogenies between supersingular elliptic curves, a result previously known only for isogenies of smooth degree. Third, there exists an unconditional probabilistic algorithm to solve the endomorphism ring problem in time O~(sqrt(p)), a result that previously required to assume the generalized Riemann hypothesis. To prove our main result, we introduce a flexible framework for the study of isogeny graphs with additional information. We prove a general and easy-to-use rapid mixing theorem. The proof of this result goes via an augmented Deuring correspondence and the Jacquet-Langlands correspondence.
• Abstract（参考訳）: 超特異自己同型リング問題(英語版)(supersingular Endomorphism Ring problem)は以下の問題である: 超特異楕円曲線が与えられたとき、その自己同型を全て計算する。 この問題の難しさは、同種暗号の基盤となる。 1 の自己同型問題は、単一の非スカラー自己同型を見つけることだけを要求する。 この2つの問題は確率多項式時間短縮の下で等価であることを示す。 私たちはいくつかの結果を証明する。 まず、自己準同型リング問題の硬さを仮定すると、Charles-Goren-Lauterハッシュ関数は衝突耐性があり、SQIsign識別プロトコルは健全である。 第二に、自己準同型環問題は超特異楕円曲線の間の任意の等元性を計算する問題と等価である。 第三に、時間 O~(sqrt(p)) における自己準同型環の問題を解くための無条件確率的アルゴリズムが存在する。 本研究の主な成果を証明するため,同種グラフ研究のためのフレキシブルなフレームワークを導入する。 我々は、汎用的で使いやすい急速混合定理を証明した。 この結果の証明は、拡張されたDeuring対応とJacquet-Langlands対応によって行われる。

関連論文リスト

• Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings [0.0]
  我々は、標数 p の超特異楕円曲線の自己準同型環を計算する決定論的時間アルゴリズムを与える。 我々は、局所自己同型環に向かうために高次元同相の技法を用いる。
  論文  参考訳（メタデータ） (2024-02-07T18:10:54Z)
• Causal Layering via Conditional Entropy [85.01590667411956]
  因果発見は、生成した観測可能なデータから観測されていない因果グラフに関する情報を回収することを目的としている。 我々は、条件付きエントロピーオラクルを介してデータにアクセスすることによって、グラフの階層化を回復する方法を提供する。
  論文  参考訳（メタデータ） (2024-01-19T05:18:28Z)
• The supersingular endomorphism ring problem given one endomorphism [5.01069065110753]
  我々は、E の自己準同型環が古典的時間で計算できることを証明した。 また、楕円曲線上の滑らかなイデアルの作用が時間内に計算できることも証明する。
  論文  参考訳（メタデータ） (2023-09-21T09:22:43Z)
• On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups [5.10647201123061]
  古典群による自然な作用の下で、d-ウェイアレイやテンソルの同型問題の複雑性について検討する。 ユニタリ群について、上記の結果は、三部分量子状態のLOCC分類が、少なくとも任意の d に対して d-部分分量子状態のLOCC分類と同じくらい難しいことを示唆している。
  論文  参考訳（メタデータ） (2023-06-05T18:00:04Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。 また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
  論文  参考訳（メタデータ） (2022-09-16T13:59:42Z)
• Failing to hash into supersingular isogeny graphs [4.57147786707036]
  重要な暗号オープン問題は、信頼できる権威なしで「ハード超特異曲線」の具体例を作成することである。 我々は、さらなる研究を刺激し、この取り組みの課題と障害に光を当てることを望んで、この問題を解決するために失敗した多くの試みを文書化しています。
  論文  参考訳（メタデータ） (2022-04-30T02:56:47Z)
• Feature Cross Search via Submodular Optimization [58.15569071608769]
  機能工学の基本的な基礎として機能横断探索について研究する。 この問題に対して単純なgreedy $(1-1/e)$-approximationアルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2021-07-05T16:58:31Z)
• Relative stability toward diffeomorphisms in deep nets indicates performance [66.51503682738931]
  微分同相性に対する安定性は、画像のベンチマークデータセットの性能と強く相関しないことを示す。 一般変換に対する微分同相性に対する安定性は、テスト誤差 $epsilon_t$ と著しく相関している。 CIFAR10と15の既知のアーキテクチャでは、$epsilon_tapprox 0.2sqrtR_f$を見つける。
  論文  参考訳（メタデータ） (2021-05-06T07:03:30Z)
• Impossibility of Partial Recovery in the Graph Alignment Problem [3.5880535198436156]
  我々は、よく知られたNPハードグラフ同型問題の平均ケースとノイズバージョンを示す。 相関式 Erd"os-R'enyi モデルでは、スパース状態における部分的回復の不可能な結果が証明される。 我々の境界はノイズのない場合(グラフ同型問題)において厳密であり、まだノイズに密接であると予想する。
  論文  参考訳（メタデータ） (2021-02-04T15:26:48Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  我々は、軽度の仮定の下で、識別性と学習可能性に関する保証を提供する。 我々は,線形制約付き結合テンソル分解に基づく効率的なアルゴリズムを開発し,スケーラブルで保証可能な解を得る。
  論文  参考訳（メタデータ） (2021-01-17T07:48:45Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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