Double Index Calculus Algorithm: Faster Solving Discrete Logarithm Problem in Finite Prime Field

技術概要：離散対数問題に対するダブルインデックス計算アルゴリズム

問題定義
本論文は、公開鍵暗号やデジタル署名を含む多数の暗号方式のセキュリティの基盤となる有限素数体における離散対数問題（DLP）を取り扱っている。インデックス計算アルゴリズムおよびその変種（数体ふるい法や関数体ふるい法など）は、これらの体における DLP を解くための最先端技術であるが、特定の限界に直面している。主に、これらのアルゴリズムは、ターゲットを解く前に、因数基底（サイズ $k$）に含まれるすべての素数およびターゲット整数に対する離散対数の計算を必要とし、合計 $k+1$ 個の対数を求める必要がある。さらに、標準的なインデックス計算アルゴリズムは、DLP の底が体の乗法生成元でない場合、因数基底内の特定の素数の離散対数が存在しない可能性があるため、しばしば失敗する。

手法：ダブルインデックス計算アルゴリズム
著者らは、「ダブルインデックス計算アルゴリズム」を提案しており、これは必要な離散対数の数を削減することで DLP を解くアプローチを根本的に変えるものである。

1. 二重方程式系: 単一のターゲット方程式を固定する代わりに、このアルゴリズムは 2 つの独立した線形方程式系を構築する。
   • 一方の系は、生成元 $g$ に関する因数基底内の素数の離散対数（$\log_g p_i$ の発見）を計算する。
   • 他方の系は、同じ素数についてターゲット底 $b$ に関する離散対数（$\log_b p_i$ の発見）を計算する。
2. 交差戦略: 核心的な革新は、因数基底内の素数 $p_i$ において、両方の $\log_g p_i$ と $\log_b p_i$ が正常に計算されたものを特定することにある。
3. ターゲット解: そのような素数が見つかった時点で、アルゴリズムは関係式 $g^x \equiv b \pmod p$ となるターゲット離散対数 $x$ を、以下の関係式を用いて解く。
   $$x \equiv \alpha \beta^{-1} \pmod{p-1}$$
   ここで、$g^\alpha \equiv p_i \pmod p$ かつ $b^\beta \equiv p_i \pmod p$ である。
4. 確率的効率性: このアルゴリズムは、滑らかな整数を見つける確率的な性質に依存している。標準的なインデックス計算アルゴリズムが $k+1$ 個の対数を決定論的に解かなければならないのに対し、ダブルインデックス計算アルゴリズムは、計算された 2 つの対数集合の交差が空でなければ成功し得る。著者らは、「好ましいケース」（$k+1$ 未満の対数でターゲットが解けるシナリオ）の数が膨大であり、早期終了の確率が高いと主張している。
5. 並列化: 底 $g$ に関する対数計算と底 $b$ に関する対数計算は独立したプロセスであるため、並列実行が可能であり、これにより総実行時間は両プロセスの和ではなく、最大値にまで削減される。

主要な貢献

• 理論的ブレイクスルー: 本論文は、必要な離散対数の数の理論的な削減を主張している。従来の手法が $k+1$ 個の対数を必要とするのに対し、提案されたアルゴリズムは、2 つの部分集合の対数の交差を利用することで、$k+1$ 未満の対数で問題を解くことができる。
• 強化された一般性: このアルゴリズムは、底 $g$ が体の乗法生成元でない場合でも動作するように設計されている。そのような場合、$\log_g p_i$ が一部の素数に対して存在しないため標準的なインデックス計算が失敗する可能性があるが、$\log_g p_i$ と $\log_b p_i$ の両方が存在する少なくとも 1 つの素数が存在する限り、ダブルインデックス計算は成功し得る。
• 互換性: この手法は、滑らかな整数の発見を加速するために使用される既存の最適化技術（ふるい法など）と互換性がある。これらの技巧を利用して滑らかな整数をより迅速に見つけ、その後、必要な滑らかな整数の数を削減する独自のロジックを適用することができる。

実験結果
著者らは、提案アルゴリズムを標準的なインデックス計算アルゴリズムおよび他の古典的な手法（ベビーステップ・ジャイアントステップ、ロ法、ポリグ・ヘルマン法）と比較する広範な実証実験を実施した。

• 高速化: ビット長が 70 の有限素数体において、ダブルインデックス計算アルゴリズムはインデックス計算アルゴリズムと比較して約 34 倍の高速化を示した（2211 秒対 75426 秒）。
• スケーラビリティ: ビット長が増加するにつれて性能の差は拡大する。50 ビットでは提案アルゴリズムは約 10 倍高速であり、70 ビットでは 30 倍以上高速であった。
• 滑らかさの上限: 実験により、提案アルゴリズムの最適な滑らかさの上限は標準的なインデックス計算とはわずかに異なることが示された（通常 $0.65B_i$ 対 $0.5B_i$ 付近）が、提案アルゴリズムはさまざまなビット長（30 から 75 ビット）にわたって一貫して低い平均実行時間を維持した。

意義と主張
本論文は、有限素数体における DLP を解くための現在の最先端技術に対する重要な改善としてダブルインデックス計算アルゴリズムを位置づけている。著者らは、計算しなければならない離散対数の数を削減することにより、アルゴリズムが計算速度の大幅な向上を達成すると主張している。彼らは、この改善が既存のふるい法の変種ではなく、解法プロセスにおける構造的な変化であると述べている。著者らは、これらの結果が、DLP の困難性に依存する暗号方式のセキュリティパラメータを研究者が選択する方法に影響を与える可能性があると示唆しており、与えられた鍵サイズの有効なセキュリティレベルは、標準的なインデックス計算の複雑さモデルによって以前に推定されていたものよりも低い可能性があるとしている。