論文の概要: Fast computation of 2-isogenies in dimension 4 and cryptographic applications
- arxiv url: http://arxiv.org/abs/2407.15492v1
- Date: Mon, 22 Jul 2024 09:19:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-23 15:31:05.256720
- Title: Fast computation of 2-isogenies in dimension 4 and cryptographic applications
- Title（参考訳）: 次元4における2-異性体の高速計算と暗号応用
- Authors: Pierrick Dartois,
- Abstract要約: 次元 $ggeq 1$ のアーベル多様体とレベル $n=2$ のtheta-coordinates の間の 2$-isogenies の連鎖を計算するアルゴリズムを提案する。
開始曲線の自己準同型環が、ラップトップ上で数秒以内に未知である場合には、SIDHに対して完全なキーリカバリ攻撃を実行することができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Dimension 4 isogenies have first been introduced in cryptography for the cryptanalysis of Supersingular Isogeny Diffie-Hellman (SIDH) and have been used constructively in several schemes, including SQIsignHD, a derivative of SQIsign isogeny based signature scheme. Unlike in dimensions 2 and 3, we can no longer rely on the Jacobian model and its derivatives to compute isogenies. In dimension 4 (and higher), we can only use theta-models. Previous works by Romain Cosset, David Lubicz and Damien Robert have focused on the computation of $\ell$-isogenies in theta-models of level $n$ coprime to $\ell$ (which requires to use $n^g$ coordinates in dimension $g$). For cryptographic applications, we need to compute chains of $2$-isogenies, requiring to use $\geq 3^g$ coordinates in dimension $g$ with state of the art algorithms. In this paper, we present algorithms to compute chains of $2$-isogenies between abelian varieties of dimension $g\geq 1$ with theta-coordinates of level $n=2$, generalizing a previous work by Pierrick Dartois, Luciano Maino, Giacomo Pope and Damien Robert in dimension $g=2$. We propose an implementation of these algorithms in dimension $g=4$ to compute endomorphisms of elliptic curve products derived from Kani's lemma with applications to SQIsignHD and SIDH cryptanalysis. We are now able to run a complete key recovery attack on SIDH when the endomorphism ring of the starting curve is unknown within a few seconds on a laptop for all NIST SIKE parameters.
- Abstract（参考訳）: 4次元異性体は、SIDH(Supersingular Isogeny Diffie-Hellman)の暗号解析のための暗号で最初に導入され、SQIsignHD(SQIsign isogenyベースのシグネチャスキーム)の派生である。
次元 2 と 3 とは異なり、ヤコビアンモデルとその微分を等元性を計算するためにもはや依存することはできない。
4次元(およびそれ以上)では、テータモデルのみを使用することができる。
Romain Cosset, David Lubicz と Damien Robert による以前の研究は、レベル $n$ coprime から $\ell$ (次元 $g$ で $n^g$ 座標を使用する必要がある)のtheta-models における $\ell$-isogenies の計算に焦点を当てている。
暗号アプリケーションでは、2ドルの異種連鎖を計算し、最先端のアルゴリズムで次元$g$で$\geq 3^g$座標を使用する必要がある。
本稿では、次元$g\geq 1$ のアーベル多様体とレベル$n=2$ のテータ座標を持つ2ドルの等質鎖を計算し、Pierrick Dartois, Luciano Maino, Giacomo Pope, Damien Robert による以前の研究を次元$g=2$ で一般化するアルゴリズムを提案する。
本稿では,これらのアルゴリズムを次元$g=4$で実装し,カニの補題から導出される楕円曲線積の自己準同型を計算し,SQIsignHDとSIDHの暗号解析への応用を提案する。
現在、全てのNIST SIKEパラメータに対して、ラップトップ上で開始曲線の自己準同型環が数秒以内に未知である場合に、SIDHに対して完全な鍵回復攻撃を実行することができる。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
例えば$binomn2-1 sum_i ne j f(x_i, x_j)$, $x_i$ は$i$thユーザへの入力を表し、ローカルモデルでは差分プライバシ(DP)である。
この定式化は、Kendallの$tau$ coefficient、Area Under Curve、Giniの平均差、Giniのエントロピーなどの重要なメトリクスをキャプチャする。
論文 参考訳（メタデータ） (2024-06-24T04:06:09Z) - Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem [12.629532305482423]
Procrustes-Wstein問題(英語版)は、2つの高次元の点雲を教師なしの設定でマッチングするものである。
2つのデータセットが$X,Y$で、$mathbbRd$の$n$データポイントで構成されています。
そこで我々は,フランク=ウルフ凸緩和法を用いて,変換とレバーベリングを代替的に推定するPing-Passerongアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-23T13:18:51Z) - The Umeyama algorithm for matching correlated Gaussian geometric models
in the low-dimensional regime [0.0]
2つの相関したランダムな幾何グラフのマッチングの問題に触発され、潜在ノード置換によって相関した2つのガウス幾何学モデルのマッチング問題を研究する。
A_i,j=langle X_i,X_j rangle$, $B_i,j=langle Y_i,Y_j rangle$ で与えられるエッジウェイトを持つ2種類の(相関した)重み付き完全グラフを考える。
論文 参考訳（メタデータ） (2024-02-23T04:58:54Z) - A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies [34.7582575446942]
多次元スケーリング(MDS)は、低次元ユークリッド空間に$n$ポイントの計量を埋め込む方法のファミリーである。
準多項式依存のMDSに対する最初の近似アルゴリズムは$Delta$である。
論文 参考訳（メタデータ） (2023-11-29T17:42:05Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Approximating Output Probabilities of Shallow Quantum Circuits which are
Geometrically-local in any Fixed Dimension [0.0]
準多項式時間における任意の逆多項式加法誤差に対して,$|x|C|0otimes n>|2$を計算できるアルゴリズムを提案する。
これは [CC21] の結果の拡張であり、元々は$D = 3$でこの結果が証明された。
論文 参考訳（メタデータ） (2022-02-16T21:37:16Z) - Learning elliptic partial differential equations with randomized linear
algebra [2.538209532048867]
ほぼ確実に収束する$G$への近似を構築することができることを示す。
0Gamma_epsilonleq 1$はトレーニングデータセットの品質を特徴付ける。
論文 参考訳（メタデータ） (2021-01-31T16:57:59Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。