比特币如何抵御量子计算机？三大格基签名方案对比

原文作者：Blockstream Team

原文编译：Saoirse，Foresight News

Blockstream リサーチは、ビットコイン向け格子ベース署名に関する完全な調査レポートを発表しました。本稿では、調査内容、主要な発見、および関連する推奨事項を要約します。完全なレポートはこちらからご覧いただけます。

デジタル署名はビットコインにおける取引承認の核心メカニズムであり、現在この機能を担うSchnorrおよびECDSA署名のコストは極めて低くなっています。1994年、Shorは、十分に強力な量子コンピュータがこれら両方の署名を解読できることを証明しました。このようなマシンがいつ実用化されるかについては依然として広く議論されていますが、問題が実際に到来する前に、実行可能な耐量子署名導入計画を策定する必要があります。

格子ベース署名方式は、既存の署名に代わる有力な候補です。格子暗号は100年以上の研究歴史を持ち、その暗号学的応用も約30年にわたって発展してきました。耐量子暗号体系において、格子ベース署名には多くの利点があります。公開鍵と署名の合計サイズは最低1.6キロバイト未満に抑えることができ、その代数構造は将来、マルチシグ、閾値署名、および簡潔な証明をサポートする可能性を秘めています。

本レポートでは、Dilithium、Falcon、Hawkの3つの方式を調査しました。格子暗号に詳しくない読者向けに、各方式の設計思想を説明し、アルゴリズムの流れを完全に紹介し、安全性、性能、実際の導入（ウォレットの鍵派生など）の観点から分析します。これら3つのうち、実際にビットコインチェーン上に導入できるのはどれでしょうか？

評価の観点

ビットコインには署名方式の選択に関する独自の制約があり、今回の評価は4つの核心基準に基づいて行われます：

• オンチェーンコスト：最も重要な指標の1つは、公開鍵と署名の合計サイズです。UTXOが消費される際、公開鍵と署名は両方ともチェーン上に記録され、全ノードはすべてのバイトをダウンロードして保存する必要があります。検証コストも同様に重要です。すべての署名はネットワーク全体のノードによって検証されるため、検証速度が遅いとネットワーク全体に負荷がかかります。
• 実装の複雑さ：方式が安全に実装できるかどうかは極めて重要です。浮動小数点演算や繊細なガウスサンプリングが必要な場合、実装ミスやタイミング分析などのサイドチャネル攻撃によって秘密鍵が漏洩する可能性があります。スムーズな移行を実現するには、実装の複雑さは無視できない要素です。
• 導入リスク：ビットコインへの実際の統合には、さまざまな現実的な障害があります。コンセンサスレイヤーでのハッシュ関数の選択（候補方式のほとんどはSHAKEを使用しますが、ビットコインはSHA-256を使用）、クロスプラットフォームでの署名結果の再現性、および署名プログラムがハードウェアウォレットのメモリ制限に適合するかどうかなどです。
• 発展可能性：大多数のビットコインウォレットはBIP-32階層的決定性メカニズムを採用しています。単一のマスター公開鍵から、秘密鍵に触れることなく、無数の子公開鍵を導出できます。現在標準化されている耐量子署名方式はこの機能をネイティブにサポートしていないため、この能力を追加するためのコストを研究し、また、より多くの利益をもたらす可能性のある非標準的な方式の変種も調査します。

どのセキュリティレベルを選択すべきか？

サイズを比較する前に、まず目標とするセキュリティレベルを決定する必要があります。この選択は見かけほど単純ではありません。NISTはセキュリティレベルを1〜5に分類しています。レベルが高いほどセキュリティは強固になりますが、対応する鍵と署名のサイズも大きくなります。

ビットコインは少なくともレベル3のセキュリティ基準を採用すべきだと考えます。ビットコインのUTXOは数十年間使われない可能性があり、暗号解読技術の進歩によって方式の実際のセキュリティレベルが低下した場合、資産は弱体化した鍵にロックされ、長期間リスクにさらされます。格子暗号の仮定は約30年にわたる公開された暗号解読に耐えており、ビットコインが楕円曲線を採用した時点での研究の蓄積よりも長い歴史があります。しかし、格子暗号の複雑な代数構造には、将来の攻撃に利用される可能性のある突破口がまだ多く残されており、遠い将来のセキュリティをすべてそこに賭けるべきではありません。

主要な製品も同じ判断を下しています。AppleのiMessage PQ3プロトコルはレベル1の格子暗号パラメータを直接放棄し、全体を通してレベル3とレベル5のパラメータを使用しています。Cloudflareは耐量子TLS導入でML-KEM-768（レベル3）を使用しており、レベル1は現時点では安全に見えるものの、今後数十年の暗号解読の進歩に備えたセキュリティマージンを確保する必要があると述べています。そしてビットコインのセキュリティタイムスパンはこれら両方よりもさらに長いものです。

セキュリティレベルを上げることにはコストが伴います。例えば、Dilithiumをレベル2からレベル3に上げると、合計サイズは約1.5キロバイト増加します。レポートでは全セキュリティレベルでのパラメータセットを比較しており、読者は各自でトレードオフを判断できます。Hawkの事例は、保守的なセキュリティ考慮が決して机上の空論ではないことを証明しています。

候補方式の詳細

Dilithium：設計がシンプルな方式

DilithiumはNISTによってFIPS 204標準のML-DSAとして標準化されており、Schnorr署名のコミットメント-チャレンジ-レスポンスのパラダイムをモジュール格子の算術に移行したものです。

その最大の特徴はシンプルさです。Dilithiumのすべての演算は整数演算です。環演算、行列ベクトル乗算、ハッシュ、丸め。浮動小数点演算はなく、離散ガウスサンプリングも必要ありません。安全で定時間の実装を書くことが容易です。また、最も広く導入されている候補であり、OpenSSL、BoringSSL、AWS-LC、Apple CryptoKitにすでに統合されています。

代償としてサイズが大きいことが挙げられます。レベル3セキュリティのML-DSA-65は、公開鍵が1952バイト、署名が3309バイトで、合計5261バイトとなり、これはビットコインのネイティブな公開鍵+署名の合計サイズの約55倍であり、同じセキュリティレベルの3つの方式の中で最大です。

ビットコインにとってDilithiumの最も価値のある点は、3つの中で唯一、BIP-32スタイルの鍵派生の実現に近いことです。再ランダム化可能な鍵構成DilithiumRKは、公開情報のみを使用して親鍵から子鍵を生成できます。レポートでは3つの変種を分析しており、その中には私たちが提案するDilithiumRKSも含まれ、派生ロジックは完全にウォレットソフトウェア内部に置かれ、チェーン上では標準の検証器が通常のML-DSA署名を処理するだけです。しかし、3つすべてがまだリリース基準に達していません。2つの変種は検証器の変更が必要であり、DilithiumRKS自体には完全な偽造不可能性の証明が欠けています。すべての方式はネットワーク全体で共有されるマトリックスに依存しており、Module-LWE仮定の下では形式的に安全ですが、すべての鍵のセキュリティを同じインスタンスに結びつけることになります。現段階では、Dilithiumベースの公開鍵派生は概念実証に過ぎず、実際の導入には耐えられないと考えています。

Falcon：サイズがコンパクトな方式

FalconはNISTによって選定され、標準化名はFN-DSAです。3つの中で最も簡潔です。レベル1セキュリティのFalcon-512の公開鍵と署名の合計は1563バイト。レベル5セキュリティのFalcon-1024の合計は3073バイトです。より高いセキュリティマージンを持つFalcon-1024は、レベル3のDilithiumよりもサイズが小さいのです。

FalconはDilithiumとは異なるアプローチを採用しています。NTRU格子に基づくハッシュアンド署名方式です。署名者の秘密鍵は格子の短い基底のセットです。メッセージはハッシュされ、空間内の1点にマッピングされます。署名者は短い基底を使用して、その点に近い格子上のベクトルを見つけます。点とその近傍ベクトルが一緒に署名を構成します。検証は、ベクトルがその格子に属し、かつ十分に近いことを確認するだけです。実装の難しさは、基底の情報を漏らさずにベクトルを見つけることにあります。初期の方式GHHやNTRUSignは最も近い格子点を直接選択しており、毎回の署名が幾何学的情報の一部を漏洩させていました。FalconはGPVフレームワークを採用し、ガウス分布から近傍ベクトルをサンプリングすることで、サンプリング出力が基底と独立であることを証明可能とし、漏洩リスクを排除していますが、サンプラーの実装難易度は大幅に上がっています。

サンプラーはFalconのエンジニアリング上の弱点です。複素フーリエ領域で演算を行い、浮動小数点計算が必要です。異なるプロセッサ、コンパイラ、コンパイル最適化オプションにより、浮動小数点の出力結果が一致しないことがあります。これは単なる互換性の問題ではなく、セキュリティ上の懸念です。GPVのセキュリティ証明は、同じダイジェストに対して署名者が2つの異なる短いベクトルを決して出力しないことを要求します。署名が決定的になると、プラットフォームによる浮動小数点の丸め差がこの条件を破壊します。実行可能な解決策があります。決定的Falconはハードウェア浮動小数点の代わりに整数シミュレーションを使用でき、すべてのプラットフォームで完全に同一の署名を出力できます。代償として、署名速度は約15倍、鍵生成速度は約2倍低下します。

重要なのは、検証プロセスは影響を受けないことです。Falconの検証は全体を通して整数演算で、結果は決定的であり、候補の中で最も検証速度が速い方式でもあります。この非対称性はビットコインにとって非常に好都合です。署名はウォレットがトランザクションを使用する際に1回実行するだけですが、すべての署名はネットワーク全体のフルノードによって検証されます。署名が15倍遅くなるのは低頻度のコストであり、クロスプラットフォームの再現性と整数演算を得るための合理的なトレードオフだと考えます。したがって、浮動小数点の問題はエンジニアリングで解決可能な障害であり、致命的な欠陥ではありません。

2つの注意点があります。構造上の制約により、Falconにはレベル3のパラメータがなく、レベル1かレベル5のいずれかを選択する必要があります。セキュリティマージンの観点から、Falcon-1024を推奨します。2点目として、署名は大量のメモリを消費します。1024パラメータセットのサンプラーは事前計算されたツリーに依存し、約90キロバイトのメモリを占有します。ハードウェアウォレットはブランチごとにこのツリーを動的に再構築でき、メモリ使用量を16キロバイトに抑えられますが、署名時間は2倍になります。ハードウェアデバイスでの署名が遅くなることは実際のコストですが、許容範囲です。

Hawk：失敗に終わった方式

Hawkの目標は、他の2つの方式の利点を融合することでした。Hawk-512の署名はわずか555バイトで、Falconよりも小さく、署名側はすべて整数演算で、最低メモリ使用量はわずか6キロバイトです。また、NIST追加署名コンペティションの第3ラウンドで唯一残った格子ベースの候補であり、レポートではこの方式に多くのページを割いています。

代償はセキュリティ仮定にあります。数十年にわたる暗号解読で検証されたNTRUやSIS問題ではなく、格子同型問題とone-more-SVP仮定に依存しています。これらの仮定は研究の歴史が比較的短いものです。

レポートの完成直前に、AnthropicのStraznickas氏とWeis氏はHawkの格子構造に構造的欠陥を発見しました。鍵回復に実際に必要なSVP問題の次元は、設計者が想定していたものの半分でした。候補パラメータセットの鍵回復セキュリティビットは大幅に弱められました。研究者らは、暗号解読用のチャレンジパラメータHAWK-256に対して完全なエンドツーエンドの鍵回復攻撃を実行しました。攻撃を受けたにもかかわらず、正式に提案されたHAWK-512およびHAWK-1024は現実的には破られませんでした。Hawkチームは攻撃の有効性を確認し、方式をNISTのプロセスから撤回しました。チームは、パラメータを2倍にして脆弱性を修正すれば、Hawkが誇っていたサイズ上の利点は完全に消えてしまうと述べています。

レポートには依然としてHawkの章が含まれています。なぜなら、この攻撃は特定の数体の代数的特性を標的としたものであり、設計パラダイム全体を否定するものではないからです。再設計によって脆弱性を回避できるかどうかは未定です。Hawkの事件は、私たちが保守的なセキュリティマージンを堅持する理由を如実に示しています。サイズが優れ、速度も十分で、標準化の複数ラウンドを経た方式であっても、1本の論文でその推定セキュリティレベルが大幅に低下し得るのです。

各方式の比較表

上表のすべての方式（SPHINCS+を含む）はステートレス署名です。署名者は過去の署名を記録する必要がありません。XMSSなどのステートフルハッシュ署名は署名サイズをさらに小さくできますが、署名状態の管理が必要です。ハッシュベース署名の専門レポートで比較をご覧いただけます。

導入には依然として多くの障壁がある

Falconには利用可能な鍵派生方式がありません。現在公開されている唯一のBIP-32スタイルのFalcon派生方式は、秘密鍵の基底を再ランダム化するもので、署名のノルム上限が急激に拡大され、オンチェーン署名は約23.7キロバイトに膨れ上がります。さらに、この方式のパラメータは自身のセキュリティ条件を満たしておらず、この問題を修正するとサイズはさらに急増します。現在、実行可能なFalcon公開鍵派生の実装はなく、これは