論文の概要: Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the
Cryptanalysis of pSIDH
- arxiv url: http://arxiv.org/abs/2305.19897v1
- Date: Wed, 31 May 2023 14:30:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 20:57:58.663812
- Title: Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the
Cryptanalysis of pSIDH
- Title（参考訳）: 隠れ安定化剤、同相環問題への異種性、およびpSIDHのクリプトアナリシス
- Authors: Mingjie Chen, Muhammad Imran, G\'abor Ivanyos, P\'eter Kutas, Antonin
Leroux, Christophe Petit
- Abstract要約: 自己同型環問題(英語版)(IsERP)は、超特異曲線の間の同型写像の余領域の自己同型環を計算することを要求する。
次数が奇数で、多くの素因子が$O(loglog p)=$である等質性に対して、IsERPを解くための新しい量子時間アルゴリズムを導入する。
- 参考スコア（独自算出の注目度）: 5.398058794903461
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the
endomorphism ring of the codomain of an isogeny between supersingular curves in
characteristic $p$ given only a representation for this isogeny, i.e. some data
and an algorithm to evaluate this isogeny on any torsion point. This problem
plays a central role in isogeny-based cryptography; it underlies the security
of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks
that broke the SIDH key exchange. Prior to this work, no efficient algorithm
was known to solve IsERP for a generic isogeny degree, the hardest case
seemingly when the degree is prime.
In this paper, we introduce a new quantum polynomial-time algorithm to solve
IsERP for isogenies whose degrees are odd and have $O(\log\log p)$ many prime
factors. As main technical tools, our algorithm uses a quantum algorithm for
computing hidden Borel subgroups, a group action on supersingular isogenies
from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a
new algorithm to lift arbitrary quaternion order elements modulo an odd integer
$N$ with $O(\log\log p)$ many prime factors to powersmooth elements.
As a main consequence for cryptography, we obtain a quantum polynomial-time
key recovery attack on pSIDH. The technical tools we use may also be of
independent interest.
- Abstract（参考訳）: 同型準同型環問題(isogeny to endomorphism ring problem、iserp)は、標数 $p$ の超特異曲線の間の同族圏の同族圏の自己準同型環を計算し、この同族関係の表現、すなわち、任意のねじれ点におけるこの同族性を評価するためのデータとアルゴリズムのみを与える。
この問題は、pSIDHプロトコル(ASIACRYPT 2022)のセキュリティの下にあり、SIDH鍵交換を破った最近の攻撃の中心にある。
この研究以前には、IsERPを一般等質次数で解く効率的なアルゴリズムは知られていなかったが、その次数が素数であるような場合が最も難しい。
本稿では、次数が奇数で、多くの素因子が$O(\log\log p)$である等質なIsERPを解くための新しい量子多項式時間アルゴリズムを提案する。
主要な技術ツールとして,隠れボレル部分群を計算するための量子アルゴリズム,eurocrypt 2021からの超特異等族に対する群作用,デューリング対応のための様々なアルゴリズム,および任意の四元数次要素を持ち上げる新しいアルゴリズムを用いて,奇数整数$n$ を$o(\log\log p)$ で修飾する。
暗号の主な結果として、pSIDHに対する量子多項式時間鍵回復攻撃が得られる。
私たちが使っている技術ツールも、独立した関心事かもしれません。
関連論文リスト
- An Attack on $p$-adic Lattice Public-key Cryptosystems and Signature Schemes [3.444630356331766]
本稿では,局所フィールドにおけるLVPアルゴリズムの改良について述べる。
このアルゴリズムを用いて上記のスキームを攻撃し、任意のメッセージをフォージし、暗号文を復号化できるようにします。
これらのスキームは壊れているが、この研究は、$p$-adic 格子が暗号プリミティブの構築に適さないという意味ではない。
論文 参考訳（メタデータ） (2024-09-13T12:31:57Z) - 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) - Efficient quantum algorithms for some instances of the semidirect
discrete logarithm problem [2.90985742774369]
SDLPは,いくつかの重要な症例においてさらに容易であることを示す。
SDLPのハードネスを前提としたセキュリティ仮定を前提としたSPDH-Signと類似の暗号系が量子攻撃に対して安全でないことを示す。
論文 参考訳（メタデータ） (2023-12-21T16:58:59Z) - Finding dense sub-lattices as low-energy states of a Hamiltonian [1.2183430883527995]
格子ベースの暗号は、量子後暗号の最も顕著な候補の1つである。
最短ベクトル問題(SVP)は、与えられた格子の中で最短の非ゼロベクトルを見つけることである。
我々は、与えられた格子の最も密度の高い$K$-Densest Sub-lattice(K$-DSP)を求めるために、$K$-Densest Sub-lattice Problem(K$-DSP)として知られるSVPの自然な一般化を研究する。
論文 参考訳（メタデータ） (2023-09-28T08:48:38Z) - Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。
このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。
Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
論文 参考訳（メタデータ） (2023-07-06T15:32:50Z) - Homomorphic Encryption of the k=2 Bernstein-Vazirani Algorithm [0.4511923587827301]
代入量子計算に有用な重要な暗号技術である量子同相暗号(QHE)へのこのスキームの適用を見出した。
我々は,完全セキュリティ,$mathcalF$-homomorphism,サーバとクライアント間の相互作用のないQHEスキームを開発し,Mが回路内のゲート数$T$である場合,$O(M)$で束縛された準コンパクト性を示す。
論文 参考訳（メタデータ） (2023-03-30T14:49:15Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - 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) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。