ビットコインは量子コンピュータにどう耐えるか？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仮定に依存しており、これら2種類の仮定は研究の歴史が比較的短い。

報告書の最終決定直前、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種類の署名体系を相互補完させることもできる。