ビットコインは量子コンピューターにどう対抗するか？3つの格子ベース署名方式を比較

原文著者：Blockstream Team

原文翻訳：Saoirse、Foresight News

Blockstream Research はビットコイン向け格子ベース署名に関する完全な研究報告書を発表しました。本記事では研究内容、主要な発見、および関連する推奨事項を要約します。完全な報告書はこちらからご覧いただけます。

デジタル署名はビットコインの取引承認の中核メカニズムであり、現在その役割を担うSchnorr署名とECDSA署名は非常に低コストです。1994年、Shorは十分に強力な量子コンピューターがあればこれら2種類の署名を破れることを証明しました。そのようなマシンがいつ登場するかについては依然として幅広い議論がありますが、問題が実際に到来する前に、実行可能なポスト量子署名の展開計画を策定しておく必要があります。

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

本報告書では、Dilithium、Falcon、Hawkの3つの方式を研究しました。格子暗号に馴染みのない読者向けに、各方式の設計思想を説明し、アルゴリズムの流れを完全に紹介し、安全性、性能、実際の展開（ウォレットの鍵導出など）の観点から分析します。3つのうち、実際にビットコインチェーンに展開できる方式はどれでしょうか？

評価基準

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

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

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

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

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

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

セキュリティレベルを上げるにはコストがかかります。例えば、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格子に基づくハッシュ-署名モードです。署名者の秘密鍵は格子の短い基底の集合です。メッセージはハッシュによって空間内の一点にマッピングされ、署名者は短い基底を用いて格子上でその点に近いベクトルを見つけます。点とその近傍ベクトルが署名を構成します。検証はベクトルがその格子に属し、かつ十分に近いことのみを確認します。実装の難しさは、基底の情報を漏らさずにベクトルを見つけることにあります。初期の方式GGH、NTRUSignは直接近くの格子点を取るため、署名のたびに幾何学的情報の一部が漏洩していました。FalconはGPVフレームワークを採用し、ガウス分布から近傍ベクトルをサンプリングします。サンプリング出力が基底と独立であることが証明可能であり、漏洩リスクを排除しますが、サンプラーの実装難度は大幅に向上します。

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

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

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

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プロセスから撤回しました。チームは、パラメータを倍増して脆弱性を修正した場合、Hawkが誇っていたサイズの優位性は完全に失われると述べています。

報告書はHawkに関する章を依然として残しています。この攻撃は特定の数体の代数的特性を狙ったものであり、この設計パラダイム全体を否定するものではないからです。再設計によって脆弱性を回避できるかどうかは、まだ結論が出ていません。Hawkの事例は、私たちが保守的なセキュリティマージンを堅持する理由を直感的に裏付けています。方式が優れたサイズと速度を持ち、標準化の複数ラウンドを通過したとしても、1本の論文でその推定セキュリティレベルが大幅に低下する可能性があるのです。

各方式の比較表

上表のすべての方式（SPHINCS+を含む）はステートレス署名です。署名者は過去の署名を記録する必要がありません。XMSSのようなステートフルなハッシュベース署名は署名サイズをさらに小さくできますが、署名状態を維持する必要があります。比較についてはハッシュベース署名の特集報告書をご覧ください。

展開には依然として多くの障壁が存在

Falconには使用可能な鍵導出方式が欠けています。現在公開されている唯一のBIP-32スタイルのFalcon導出方式は、秘密鍵の基底を再ランダム化するため、署名ノルムの上限が急激に拡大し、オンチェーン署名は約23.7キロバイトに膨れ上がります。さらに、その方式のパラメータは自身のセキュリティ条件を満たしておらず、その問題を修正するとサイズはさらに急増します。現時点では実行可能なFalcon公開鍵導出の実装は存在せず、これは報告書が提起する最も価値のある未解決問題です。

Falcon標準はまだ最終決定されていません。NISTはFalconを選定しましたが、FN-DSA草案はまだ正式に公開されていません。標準化が完了すれば、監査済みの実装、テストベクトル、ハードウェアレベルのサポートがもたらされます。広範な展開はビットコインのコンセンサス層への統合リスクと難度を低減します。私たちはFN-DSAの正式公開を待つことを推奨します。それまではFalconは依然として変更される可能性があります。

Falcon-WSバリアント：このバリアントは内部パラメータを緩和し、棄却サンプリングで補償します。レベル1の合計サイズは1114バイト、レベル5は2387バイトに圧縮され、オリジナルのFalconよりもさらにサイズが削減されます。この方向性は研究価値がありますが、公式標準には組み込まれず、より多くの暗号解析による検証が必要です。すでに、その派生方式の強偽造不可能性の証明に脆弱性があることが発見されています（通常の偽造不可能性には影響しません）。

将来、より優れた方式は登場するでしょうか？上記の方式以外にも、Fiat-Shamir系列は2013年のBLISSに端を発し、CRYPTO 2025会議でGärtnerが発表した最新の成果は、成熟した仮定に基づき、紙面上のサイズはFalconに匹敵します。この系列がエンジニアリングとして実装しにくい根本原因は、実装のセキュリティ問題にあります。BLISSはガウスサンプリングが定数時間でないためにサイドチャネル攻撃で破られたことがあります。後続の方式もこの問題を完全には解決しておらず、最新の成果もサンプリングプロセスの防御がより困難であることを示唆しています。この問題が解決されるまで、この種の方式は理論的な魅力しかなく、展開には適していません。

格子ベース署名とハッシュベース署名は補完可能です。格子ベース署名はハイブリッド方式のコンポーネントとして使用できます。例えばSHRINCSでは、ステートレス回復パスは現在数KBのSPHINCS+署名を使用しています。これをFalcon（またはFalcon-WS）署名に置き換えると、サイズが小さくなり、検証が高速になり、低頻度の回復パスのオーバーヘッドが大幅に削減され、日常使用パスには影響しません。

研究の結論

格子ベース候補方式の優劣は明確です。HawkはAnthropicチームの攻撃を受けて競争から脱落しました。Dilithiumは実装難度が最も低く、鍵導出に関する研究基盤を持つ唯一の方式ですが、サイズがビットコインのオンチェーンコストにとって好ましくありません。Falconはコンパクトなサイズ、高速な検証、成熟したセキュリティ仮定を兼ね備えています。その主な弱点である署名側の浮動小数点演算には、すでに実行可能なエンジニアリングソリューションが存在します。今すぐビットコイン向けに格子ベース署名方式を選択しなければならない場合、私たちはFalcon-1024を選びます。

現時点では、私たちの見解はハッシュベース署名の報告書と一致しています。短期的な保守路線は依然としてハッシュベース署名であり、セキュリティ仮定が最も成熟しており、リスクが最も低く、移行方式として適しています。FN-DSAが正式に確定し、安定した仕様、監査済みのコードベース、ハードウェアウォレットのサポートが整った後には、Falconは純粋なハッシュ署名と比較して大幅な改善をもたらすでしょう。また、ハイブリッド展開を採用し、2つの署名体系を相互に補完させることも可能です。