Blockstream Researchは、ビットコイン向け格子ベース署名に関する完全なレポートを公開しました。本記事では調査内容、判明したこと、推奨事項を要約します。レポート本体はePrintで公開しています。
デジタル署名はビットコインでトランザクションを承認する中核機構であり、現在使われるSchnorr署名とECDSA署名は非常に低costです。しかしShorは1994年、十分に大きな量子コンピューターがこれらを破れることを示しました。そのような機械がいつ実現するかは現在も議論されていますが、答えが現実的な問題となるより前に、耐量子署名の信頼できる導入計画が必要です。
格子ベース署名方式は、有力な代替候補です。格子は100年以上、暗号への応用は約30年研究されてきました。耐量子方式のなかでも、署名と公開鍵の合計sizeを1.6KB未満から実現でき、将来的にはmultisignature、threshold signing、succinct proofを支え得る代数構造を備えています。
レポートではDilithium、Falcon、Hawkの3方式を研究しました。格子暗号の予備知識を前提とせず、それぞれの設計の直感、algorithmの完全な説明、security、performance、wallet key derivationなどの導入面を分析しています。本記事では「3方式のうち、実際にon-chainへ導入できるものはあるか」という結論を要約します。
評価基準
On-chain cost：公開鍵と署名はoutput使用時にon-chainへ記録され、全full nodeが各byteをdownload・保存するため、両者の合計sizeが重要です。各署名を全nodeが検証するため、検証costもネットワーク全体へ影響します。
実装の複雑さ：方式を安全に実装できるかも重要です。浮動小数点演算や繊細なGaussian samplingを必要とする設計は、実装ミスやtiming analysisなどのside-channelによって秘密鍵を漏えいする可能性があります。円滑な移行には実装の複雑さを考慮する必要があります。
導入上の問題：候補が使うSHAKEとビットコインが使うSHA-256というconsensus-criticalなhash functionの選択、platform間の署名再現性、hardware walletのRAMに収まるかなど、実際の統合で生じる摩擦を検討します。
可能性：多くのビットコインウォレットは階層的・決定論的（BIP32）で、ひとつのmaster public keyから秘密鍵に触れず無制限にchild public keyを導出できます。標準化済み耐量子方式はそのままでは対応しないため、追加costを調べ、未標準ながら利点をもたらす変更も検討します。
どのSecurity Levelを選ぶか
Size比較の前に目標security levelを決める必要があります。NISTはsecurity category 1～5を定義しており、高いcategoryほど安全性が高い一方、鍵と署名も大きくなります。
ビットコインでは最低でもcategory 3を目指すべきです。Outputは数十年使われないことがあり、暗号解析の進展で想定security levelが下がると、弱体化した鍵にcoinが長期間ロックされ、無期限に危険へさらされます。格子仮定は約30年公開分析されてきましたが、豊かな代数構造は将来の攻撃余地を増やします。
主要な導入者も同じ結論です。AppleはiMessage PQ3 protocolでcategory 1格子parameterを採用せずcategory 3と5を使い、Cloudflareは耐量子TLSでML-KEM-768（category 3）を導入しています。ビットコインの時間軸はどちらよりも長いものです。
安全余裕には代償があります。Dilithiumをcategory 2から3へ上げると合計sizeが約1.5KB増えます。レポートは全categoryのparameter setを比較しています。後述するHawkの事例は、慎重さが理論上だけの問題ではないことを示しています。
候補方式
Dilithium：分かりやすい方式
NISTがFIPS 204のML-DSAとして標準化したDilithiumは、Schnorrと同じcommitment–challenge–response templateをmodule lattice演算へ移したものです。
最大の特徴は単純さです。演算はring arithmetic、matrix-vector積、hashing、roundingという整数演算だけで、浮動小数点やdiscrete Gaussian samplingがありません。安全なconstant-time実装を作りやすく、OpenSSL、BoringSSL、AWS-LC、Apple CryptoKitですでに採用されています。
代償はsizeです。Category 3のML-DSA-65は公開鍵1,952バイト、署名3,309バイト、合計5,261バイトで、ビットコインの公開鍵・署名合計の約55倍です。全security levelで3候補中最大です。
ビットコインにとって興味深いのは、BIP32型key derivationに近い実用案を持つ唯一の候補であることです。DilithiumRKは公開情報だけでparent keyからchild keyを作ります。レポートでは、導出logicをwallet softwareだけに置き、chain上では標準verifierによる通常のML-DSA署名として見える提案DilithiumRKSを含む3方式を分析しました。しかし2方式は標準外verifierが必要で、DilithiumRKSはunforgeability proofが未完成です。すべてnetwork-wideの共有matrixへ依存し、Module-LWE上は正当でも全鍵の安全性を単一instanceへ集中させます。現時点ではproof of conceptで、導入可能な選択肢ではありません。
Falcon：小型な方式
NISTがFN-DSAとして標準化対象に選んだFalconは3方式で最小です。Category 1のFalcon-512は公開鍵と署名で1,563バイト、category 5のFalcon-1024は3,073バイトです。大きな安全余裕を持つFalcon-1024でもcategory 3のDilithiumより小さくなります。
FalconはNTRU lattice上のhash-and-signを用います。秘密は格子の短いbasisで、messageを空間内の点へhashし、短いbasisを使って近くのlattice vectorを探します。この組が署名となり、検証ではvectorが格子上にあり十分近いことだけを確認します。Basisを漏らさずvectorを探すことが難点です。旧方式は近傍へ単純にroundingし、署名ごとに幾何情報を漏らしました。FalconはGPV frameworkに従い、basisから統計的に独立したGaussian分布からvectorをsampleしますが、samplerが複雑になります。
実用上の弱点は、複素数上のFourier domainで動く浮動小数点samplerです。結果がprocessor、compiler、optimization flagで異なる可能性があります。Derandomized signingで同じdigestに異なる短いvectorを返すとGPV proofの要件を破ります。解決策として、hardware浮動小数点を整数emulationへ置き換えるdeterministic Falconがあり、全platformでbit単位に同じ署名を生成します。署名は約15倍、鍵生成は2倍遅くなります。
検証には浮動小数点を使わず、整数だけで決定論的に動き、候補中最速です。1つのwalletが一度行う署名に15倍のcostを課し、全full nodeが行う検証を速く保つ非対称性はビットコインに適しています。このため浮動小数点要件はblockerではなく、管理可能なengineering課題です。
注意点は2つあります。構造上category 3 parameterがなく、category 1か5のみなので安全余裕からFalcon-1024を推奨します。また1024 levelのsampler用precomputed treeは約90KBのRAMを使います。Hardware walletでは約16KBでbranchごとに再構築できますが、署名時間が約2倍になります。小型deviceで遅くなる代償は現実的ですが、管理可能と考えられます。
Hawk：成立しなかった方式
HawkはFalconより小さい署名（512 levelで555バイト）と、RAM 6KBで動く単純な整数演算signerを組み合わせることを目指し、NIST追加署名competitionの第3roundに残った唯一の格子候補でした。
一方、安全性は長年分析されたNTRUやSISではなく、比較的新しいLattice Isomorphism Problemとone-more-SVP仮定に依存しました。
レポート完成直前、AnthropicのStraznickasとWeisがHawkの格子構造に構造的弱点を発見しました。鍵回復が設計者の想定した約半分の次元の格子でSVPを解くことに依存しており、推定costから数十bitが失われました。暗号解析challenge用HAWK-256に対する完全な鍵回復も実証されました（HAWK-512と1024は攻撃後も実用範囲外です）。Hawk teamは攻撃を確認してNIST processから撤退し、parameterを倍増する修正では小型という利点が消えると説明しました。
攻撃は設計paradigm全体ではなく、選択したnumber field固有の代数的特徴を利用するため、Hawkの章はレポートに残しました。再設計で回避できるかは未解決です。標準化第3roundまで進んだ小型で高速な方式でも、1本の論文によって推定securityの大部分を失い得ることを示し、保守的な仮定と安全余裕の重要性を明確にしています。
方式ごとのサイズ
| 方式 | NIST category | 公開鍵 | 署名 | 合計 |
|---|---|---|---|---|
| Schnorr (secp256k1) | 量子以前 | 32 B | 64 B | 96 B |
| Falcon-512 | I | 897 B | 666 B | 1,563 B |
| Falcon-1024 | V | 1,793 B | 1,280 B | 3,073 B |
| Dilithium-2 | II | 1,312 B | 2,420 B | 3,732 B |
| Dilithium-3 | III | 1,952 B | 3,309 B | 5,261 B |
| Dilithium-5 | V | 2,592 B | 4,627 B | 7,219 B |
| HAWK-512 | 撤回 | 1,024 B | 555 B | 1,579 B |
| HAWK-1024 | 撤回 | 2,440 B | 1,221 B | 3,661 B |
| SPHINCS+-128s | I | 32 B | 7,856 B | 7,888 B |
表の方式はSPHINCS+を含めすべてstatelessです。XMSSなどのstateful hash-based方式はstate管理と引き換えに小さい署名を実現します。比較はhash-based reportをご覧ください。
導入を決定できない理由
Falconにkey derivationがない：公開済みのBIP32型方式は秘密basisをrerandomizeし、signature norm boundを大幅に増やして署名を約23.7KBにします。提案parameterは方式自体のsecurity条件も満たさず、修正するとさらに大きくなります。実用的なpublic-key derivationがないことは重要な未解決問題です。
Falcon標準が未完成：NISTはFalconを選定しましたがFN-DSA draftは未公開です。標準化によって監査済み実装、test vector、hardware対応が整い、consensus-criticalな統合を安全にします。標準公開までは仕様が動くため、待つべきです。
Falcon-WS：内部parameterを緩和しrejection samplingで補う最近のvariantは、合計sizeをcategory 1で1,114バイト、category 5で2,387バイトにします。有望ですが標準に含まれない可能性が高く、追加暗号解析が必要です。後続研究のstrong-unforgeability proofにはすでにgapが見つかっています（通常のunforgeabilityには影響しません）。
より良い方式が現れる可能性：2013年のBLISSに始まるFiat-Shamir系統では、CRYPTO 2025のGärtnerらの方式が成熟した仮定のもとFalcon並みのsizeを実現します。しかしBLISSはconstant-timeでないGaussian samplingへのside-channelで破られ、後続方式も解決していません。実装securityが改善するまでは、理論上魅力的でも導入できません。
格子とhashは相互補完的：格子方式をhybrid方式の一部にもできます。SHRINCSのstateless recovery経路は現在数KBのSPHINCS+署名ですが、FalconまたはFalcon-WSなら小さく高速に検証でき、日常利用経路を変えず低頻度のfallbackを安くできます。
結論
格子候補の順位は明確です。Hawkは攻撃後に撤回されました。Dilithiumは実装が最も容易でkey derivation案もありますが、ビットコインにはsizeが大きすぎます。Falconは小型、検証速度、成熟した仮定の組み合わせが最良で、浮動小数点署名という欠点には既知の実用的対策があります。今日ビットコイン向け格子署名を選ぶならFalcon-1024です。
ただし現時点の見解はhash-based reportから変わりません。短期的に保守的な選択肢は、最も成熟した仮定へ依存しriskが小さいhash-based方式です。FN-DSAが確定し、固定仕様、監査済みlibrary、hardware対応が整えば、Falconは純粋なhash-based署名を大きく改善でき、hybrid導入で両方式を補完できます。
格子暗号の予備知識を前提としないalgorithm説明、security分析、parameter導出、wallet derivation方式を含む完全なレポートはePrintで公開しています。
Blockstream ResearchをXでフォローし、今後の記事をnewsletterでお受け取りください。
原文：Falcon, Dilithium, and the Fall of Hawk: Evaluating Lattice-Based Signatures for Bitcoin
