Logarithmic Density of Rank $\geq 1$ and Rank $\geq 2$ Genus-2 Jacobians and Applications to Hyperelliptic Curve Cryptography

技術要約：ランク $\ge 1$ および ランク $\ge 2$ の種数 2 ヤコビアンの対数密度と、ハイパー楕円曲線暗号への応用

問題設定
本論文は、$\mathbb{Q}$ 上で定義された種数 2 の曲線のヤコビアンにおける Mordell–Weil ランクの定量的分布に対処している。Mordell–Weil の定理は、有理点の群が有限のねじれ部分群と自由アーベル群（ランク $r$）に分解することを保証しているが、算術的な大きさによって順序付けられた族の中で、ランク $r \ge 1$ または $r \ge 2$ となる曲線の頻度を理解することは、算術幾何学における中心的な課題である。具体的には、整数 Weierstrass モデルのナイーブな高さによって順序付けられたハイパー楕則曲線に対して、これらの分布を調査している。二次的な目的は、分割されたヤコビアンを持つ、二次および二重二次ツイストの族内でのランク分布を分析し、離散対数問題（DLP）に対する Regev の量子アルゴリズムへの有用性を評価することである。

手法
著者らは、幾何学的、解析的、および計算的な手法を組み合わせて用いている：

1. 幾何学的枠組みと普遍的切断： 本研究は、整数 Weierstrass モデル $y^2 + h(x)y = f(x)$ のパラメータ空間を利用している。著者らは、普遍的ヤコビアン上の普遍的切断 $\alpha_{\text{univ}} = [\infty_+ - \infty_-]$ を定義しており、これは 2 つの無限遠点間の差に対応する。彼らは、この切断が生成ファイバーにおいてねじれではないことを証明している。
2. ねじれ軌跡と高さの境界： $\alpha_{\text{univ}}$ がねじれ点に特化するパラメータの軌跡が、より低い次元の Zariski 閉集合であることを確立することにより、また（Faltings 高さや $\theta$-高さの比較を用いて）ねじれ部分群のサイズを曲線の高さに対して抑えることにより、高さの境界 $X \to \infty$ のとき、この切断がねじれとなる曲線の割合がゼロに収束することを示す。
3. Néron 特化： ランク $\ge 2$ を確立するために、著者らは、2 つの独立した切断（一方は $\alpha_{\text{univ}}$ であり、もう一方は特定の特化によって構成されるもの）が生成的に独立であるような、明示的な 2 パラメータの部分族を構築する。彼らは Néron の特化定理を適用し、ほとんどすべての特化において、ランクが少なくとも 2 以上であることを示す。
4. 分割されたヤコビアンの構成： 分割されたヤコビアン（楕円曲線の直積に同種であるもの）を持つ曲線について、著者らは、連結（gluing）構成（Gajović–Park および [33] に従う）を利用して、種数 2 のヤコビアンのランクと構成要素である楕円曲線のランクを関連付ける。彼らは、これらの分割された曲線の二次および二重二次ツイストの族を分析する。
5. 計算による検証： 理論的な結果は、LMFDB での明示的な探索およびカスタムスクリプト（GitHub リポジトリで利用可能）による検証によって支持されている。これらは、独立した切断の検証や、CM 曲線および分割ヤコビアン曲線を用いた暗号で使用される特定の族のランク計算を行う。

主要な貢献と結果

• ランク $\ge 1$ の対数密度： 著者らは、2 つの有理無限遠点を持つ種数 2 の曲線（これにより切断 $\alpha_{\text{univ}}$ の存在が保証される）の集合が、高さによって順序付けられた整数モデルの族に関して、少なくとも $13/14$ の対数密度を持つことを証明している。この切断は、ほとんどのモデルにおいて非ねじれであるため、これはランク $r \ge 1$ の曲線に対する無条件の下限として、少なくとも $13/14$ の対数密度を与える。
• ランク $\ge 2$ の対数密度：
  • 2 つの独立した有理切断を持つ明示的な部分族を構築することにより、著者らは、ランク $r \ge 2$ の曲線に関する無条件の対数密度が少なくとも $5/7$ であることを示す。
  • また、分割されたヤコビアンとランク $r \ge 2$ を持つ曲線の部分族を特定し、少なくとも $2/21$ の対数密度を得ている。
• ツイストの族：
  • （$E_1, E_2$ が完全な有理 2 捩れを持つ）$E_1 \times E_2$ に同種である分割されたヤコビアンを持つ種数 2 の曲線について、Birch–Swinnerton-Dyer (BSD) 予想を仮定すると、著者らは、二重二次ツイストの族が、ランク $\ge 2$ の曲線を正の割合（$1/4$）で含むことを示す。
  • ヤコビアンが $E^2$ に同種であり、$E$ が有理 3-isogeny を持つ曲線については、二次ツイストの族がランク $\ge 2$ の曲線を正の割合で含むことを無条件に証明する。
• 暗号学的含意： 本論文は、Regev の量子アルゴリズムの文脈における「高ランク曲線問題」および「高ランクツイスト問題」を分析している。Regev のアルゴリズムは、有理的なリフトまたは適合するツイストのランク $r$ に対して $d = r + 2$ というパラメータを利用する。結果は、高ランクの曲線（またはツイスト）を見つけることが、素朴なブルートフォース探索よりも大幅に効率的であることを示唆している。該当する高さの順序付けにおいて、複雑度は $O(X^7)$ から、ランク $\ge 1$ では $O(X^{1/2})$ へ、ランク $\ge 2$ では $O(X^2)$ へと減少する。著者らは、$y^2 = x^5 + a$ や分割ヤコビアンの族など、ハイパー楕円曲線暗号（HECC）で使用される曲線の高ランク・ツイストの具体例を提示し、計算可能な探索空間内にランク 6 からランク 8 のツイストが存在することを示している。

意義
本論文は、ナイーブな高さによって順序付けられた、正の Mordell–Weil ランクおよびランク 2 以上の種数 2 の曲線の対数密度に関する、初の無条件の下限を提供する。これは、ランダム行列モデルからのヒューリスティックな予測を超え、厳密な幾何学的証明へと進展させたものである。

その意義は二重である：

1. 算術幾何学： 本研究は、高ランク曲線の存在と密度を定量的な方法で解決しており、高ランクの曲線が（対数的な意味で）これまで定量化されていたよりもはるかに密な集合であることを示している。ランク $\ge 2$ の曲線を持つ明示的な部分族の構成は、そのような曲線の具体的なソースを提供する。
2. 暗号解読： この結果は、Regev の量子アルゴリズムに対するハイパー楕円曲線暗号のセキュリティ分析に直接影響を与える。高ランクのツイストやリフトの豊富さを定量化することで、本論文は、Regev 型のアルゴリズムに必要な Mordell–Weil 生成元を供給するための「前処理」ステップが、幅広い曲線族（分割ヤコビアンを含む）において計算可能な範囲内であることを示唆している。これは、そのような高ランク構造が存在する場合、パラメータ $d$ を増大させることができ、量子回路のサイズを縮小できるため、特定の攻撃に対する実効的なセキュリティが予想よりも低くなる可能性があることを意味している。

著者らは、暗号学的含意に関して控えめなトーンを維持しており、彼らの研究は安全な曲線の選択を推奨するものではなく、むしろ Regev 型の攻撃のための「入力」として適した曲線を特定するものであることを明確にしている。彼らは、これらの構造が高ランクの前処理を容易にするものの、それが一般的な種数 2 のヤコビアンに対する既存の手法よりも高速な離散対数アルゴリズムを現時点で意味するものではないことを強調している。むしろ、特定の量子攻撃をより実行可能なものにするものである。