技術要約: TALUS – 1ラウンド・オンライン署名を実現する閾値ML-DSA

1. 問題提起

ML-DSA（CRYSTALS-Dilithiumに基づくFIPS 204）を閾値設定でデプロイすることは、その固有の非線形な丸めステップのために、長年の未解決問題であった。Schnorr/ECDSA向けのFROSTのような古典的な閾値署名が加法準同型性に依存しているのに対し、ML-DSAは、署名のヒントが範囲内に収まっていることを保証するために、二次的な残差 $r_0 - cs_2$ のチェックを必要とする。閾値設定では、秘密鍵のコンポーネント $s_2$ が各パーティ間で共有される。この $r_0$ チェックを扱うための従来のアプローチは、以下のいずれかを必要としていた：

1. 高コストなMPC: $cs_2$ をオンラインで評価するためのマルチパーティ計算。
2. 信頼されたコーディネーター: TEE（Trusted Execution Environment）または単一の信頼されたパーティに $s_2$ を保持させる。
3. ノイズ・フラッディング: チェックを隠蔽するためにパラメータを劣化させる。

これらの手法は、オンライン・レイテンシを増大させる（複数ラウンド）、信頼モデルを制限する、あるいはセキュリティパラメータを低下させる。さらに、根本的な「格子閾値のトリレンマ（Lattice Threshold Trilemma）」が存在する。すなわち、ノンス空間からの群準同型は、隠蔽性と拘束性を同時に満たすことができないため、離散対数設定で使用される標準的な準同型コミットメントスキームは適用できない。

2. 手法と中核となる革新

TALUS（Threshold Agile Lattice Unified Signatures）は、オンライン署名フェーズから $r_0$ チェックを切り離し、新しい代数フレームワークを通じて分散コミットメント問題を解決することで、これらの障壁を克服する。

2.1 境界クリア条件 (Boundary Clearance Condition: BCC)

本論文は、ML-DSAのコミットメント空間における幾何学的特性を特定している。署名プロセスには残差 $r_0 = \text{LowBits}(Ay)$ が関与する。秘密鍵に依存するシフト $cs_2$ は、$r_0$ がモジュロ境界（$\pm \gamma_2$）に近い場合にのみ、丸めの境界を越える可能性がある。

• 観察: すべての $r_0$ の係数が、境界から $\beta = \tau\eta$（$\tau$ はチャレンジの重み、$\eta$ は秘密鍵の境界）よりも離れている場合、シフト $cs_2$ は境界を越えることができない。
• 含意: この境界クリア条件 (BCC) の下では、コミットメントの高次部分（$w_1$）は $s_2$ によって変化せず、ヒント $h$ は公開値（$r = Az - ct_1 \cdot 2^d$ および $w_1$）のみから計算可能となる。
• 確率: BCCが満たされる確率は、ノンス試行1回あたり $p_{BCC} \approx 31.7\%$ である。
• 戦略: TALUSは、BCCを満たすノンスを生成するためのオフライン・プリプロセッシングを行う。これにより、署名中のオンラインフェーズの前に「不適切な」ノンスを排除し、$s_2$ の計算や $r_0$ のチェックを不要にする。

2.2 キャリー除去フレームワーク (Carry Elimination Framework: CEF)

BCCがある場合でも、パーティはコミットメント・ハッシュ入力 $w_1 = \text{HighBits}(Ay)$ を分散的に計算しなければならない。$\text{HighBits}$ は群準同型ではないため、個々のノンスのシェア $w_{1,i}$ を加算すると「キャリー（繰り上がり）」が発生し、これを解決する必要がある（ただし、完全なノンスを再構成することなく）。

• 主要な恒等式: 本論文は、モジュロ恒等式 $\alpha^{-1} \equiv -16 \pmod q$ （ここで $\alpha = 2\gamma_2$）を利用している。
• プロトコル:
  • TALUS-TEE: 信頼されたコーディネーター（TEE内）が総和ノンスを保持し、$w_1$ を直接計算する。
  • TALUS-MPC: パーティはキャリー安全比較プロトコル (CSCP) を使用する。彼らは、加法的なノンスの断片のマスクされた分解をブロードキャストする。Beaverトリプルとプレフィックスツリー比較回路を用いることで、パーティは単一のキャリービット $c$ とFIPS補正ビット $\delta$ を計算できる。これにより、コーディネーターは個々のノンスの低次ビットを知ることなく、正確な $w_1$ を再構成できる。
• 効率性: $T=2$ の場合、これは分散比較関数 (DCF) に退化し、通信量を大幅に削減する。$T \ge 3$ の場合、オフラインで $O(\log N)$ ラウンドを必要とするが、オンラインフェーズには影響しない。

3. プロトコルのインスタンス化

本論文では、2つのデプロイメント・プロファイルを示す。

TALUS-TEE (Trusted Execution Environment)

• モデル: コーディネーターが $s_2$ と $t_0$ をTEE内に保持する。署名者は $s_1$ のシェアを保持する。
• プロセス: TEEはBCCに適合するノンスを見つけるためのオフライン・プリプロセッシングを行う。その後、$w_1$ をブロードキャストする。署名者は $z_i = y_i + c \cdot s_{1,i}$ で応答する。TEEは署名を組み立てる。
• 信頼: 準同型（semi-honest）なTEEコーディネーターを必要とする。署名者は悪意を持つことが可能である（識別可能な中断：Identifiable Abort）。
• 制約: 正当な多数派（Honest-majority）の要件はない（$N \ge T$）。

TALUS-MPC (完全分散型)

• モデル: 完全分散型であり、どのパーティも $s_2$ や総和ノンスを保持しない。
• プロセス: パーティはオフライン・プリプロセッシング中にCEFを介して $w_1$ を共同計算する。オンライン署名はTEEと同一である。
• 信頼: 識別可能な中断（IA）を伴う悪意のあるセキュリティ（$T \ge 2$）。
• 制約: $T \ge 3$ の場合、ラッシング攻撃者（rushing adversary）がノンスの低次ビットを学習することを防ぐために、正当な多数派（$N \ge 2T - 1$）が必要である（「不誠実な多数派の障壁」）。$T=2$ の場合は、正当な多数派は必要ない。

4. 主な貢献

1. 格子閾値のトリレンマ: 格子ノンス空間からの群準同型は、隠蔽性と拘束性を同時に満たすことはできないという証明。これは、キャリー解決がFIPS互換の格子閾値スキームにおける数学的必然であることを示しており、単なるプロトコルの副産物ではないことを確立している。
2. 境界クリア条件 (BCC): $r_0$ チェックを約31.7%のノンスに対してバイパスできることを形式的に証明し、オンラインフェーズにおける $s_2$ 計算の排除を可能にした。
3. キャリー除去フレームワーク (CEF): $y$ を再構成することなく $\text{HighBits}(Ay)$ を計算する分散プロトコル。ML-DSAの特定のモジュロ算術特性を利用している。
4. 1ラウンド・オンライン署名: 両方のバリアントにおいて、単一のブロードキャストラウンドによるオンライン署名を達成しており、単一パーティ署名のレイテンシに一致する。これは、2〜3ラウンドを必要とする先行研究（Mithril, Quorusなど）よりも優れた性能である。
5. 実装: 全てのFIPS 204セキュリティレベル（ML-DSA-44, 65, 87）に対応したRustのリファレンス実装。

5. 結果とパフォーマンス

• 成功率: 成功する署名1回あたりの期待されるプリプロセッシング試行回数は、約3.15回である（BCC通過率31.7%による）。
• レイテンシ (ML-DSA-65, $T=3$):
  • TALUS-TEE: オンライン署名は 0.29 ms。合計（オフライン準備を含む）のアンバamortized（償却）時間は 1.52 ms。
  • TALUS-MPC: オンライン署名は 0.68 ms。合計のアンバamortized（償却）時間は 4.09 ms。
  • 比較: TALUS-TEEは、オンライン・レイテンシにおいてMithril（3.6 ms）より 2.4倍高速 である。TALUS-MPCはMithrilと同等の性能であるが、Mithrilの3ラウンドに対し、TALUSはシングル・オンライン・ラウンドを実現している。
• 通信量:
  • T=2: オフラインコストは1バッチあたり約5 KB (DCF)。
  • T $\ge$ 3: オフラインコストは1バッチあたり約350 KB (CarryCompareに支配される)。
  • オンライン: 約3.6 KB/署名で一定であり、$T$ および $N$ に依存しない。
• ネットワーク・レイテンシ: 分散環境（GCP）での実験において、エンドツーエンドのレイテンシはネットワークRTT（例：US-Europe間 $\approx 350$ ms）に対して線形にスケールしており、シングルラウンドの優位性を裏付けている。

6. 意義と主張

本論文は、TALUSが以下のすべてを同時に達成する最初の閾値ML-DSA構成であると主張している：

1. 完全なFIPS 204互換性: 署名は、修正されていない標準的な検証者によって検証可能である。
2. 任意の閾値: $1 \le T \le N$ の任意の $T$-of-$N$ をサポートする（MPCの $T \ge 3$ における特定の正当な多数派の制約はある）。
3. 1ラウンド・オンライン署名: 単一パーティ署名のレイテンシに一致し、複数のオンラインラウンドを必要とする先行研究に対する大幅な改善を実現している。

著者らは、「キャリー・コスト」は格子設定における固有の代数的代償であるが、TALUSはこれを完全にオフラインフェーズに移行させることで最小化していると強調している。本研究は、FIPS 204への互換性が、閾値設定においてパフォーマンスの低下を必ずしも強いるものではないことを示している。

注記（暗号解読について）: 本論文には、G. Niotによる暗号解読（2026-07-09付）を認める記述が含まれている。その攻撃により、TALUS-MPCにおけるコミットメントスキームが隠蔽性を欠いていること（$Ax$から$x$を復元可能であること）、および$s_2$チェックの除去が統計的な漏洩を導入していることが確認された。著者らはこれらの点について認め、$As_{1,i}$の隠蔽性と$s_2$ チェックの秘匿性に関する冗長性に関する特定の主張を撤回し、真に隠蔽的なコミットメントを用いた改訂版の構成を準備中であると述べている。また、TALUS-TEEはこれらのコミットメント攻撃の影響を受けないと述べている。