SHRINCSのパラメータ探索

ビットコイントランザクションは、楕円曲線暗号に基づくSchnorr署名とECDSA署名で保護されています。十分な能力を持つ量子コンピューターが実現すると、公開された公開鍵から秘密鍵を復元し、その鍵が保護する資金を使用できる可能性があります。そのような機械がいつ、あるいは本当に実現するかは誰にも分かりません。しかしビットコインを新しい暗号へ移行するには何年もかかるため、脅威が現れるより十分早く準備を始める必要があります。

量子コンピューティングがビットコインに与える影響の全体像は、Blockstreamの量子コンピューティングページをご覧ください。

SHRINCSは、ビットコインで実用的に利用できる耐量子方式としてBlockstream Researchが提案したハッシュベース署名方式です。ひとつの公開鍵に2つの署名経路を持たせます。日常利用向けの小さなstateful経路では、署名が324バイトから始まり、追加署名ごとに約16バイト増えます。署名者がstateを失っても利用できるstateless fallbackも備えますが、署名は大きくなります。安全性は、ビットコインがマイニングとアドレスですでに利用するSHA-256だけに依存します。Blockstream Research DirectorのJonas Nickは、OP_CHECKSHRINCSの記事で設計を詳しく紹介しています。

ハッシュベース署名方式には、形状、サイズ、鍵生成・署名生成・検証など基礎関数のcostを決めるparameter群があり、選択ごとに指標間のtrade-offが生じます。ビットコインでは署名byteがblock spaceを使用し、全nodeが署名を検証し、resourceの限られたhardware walletでも署名と鍵を生成する必要があります。したがって、この選択が耐量子署名の実用性を左右します。SHRINCSでは、ビットコイン用途で実用的な範囲に保ちながら最短の署名を探しました。

本記事では25,935個の候補を探索し、SLH-DSAより約25%小さく、署名生成・検証costもわずかに低いstateless fallbackへ到達した過程を示します。選択を誰でも検証できるオープンソースExplorerも構築しました。

Stateless fallbackの構造

SPHINCS+署名は、Merkle treeの層（hypertree）と、そのleafに配置されたfew-time signature（FORS）で構成されます。各層はone-time Winternitz signatureで結合されます。NISTはSPHINCS+をFIPS 205のSLH-DSAとして標準化しており、以下ではこの名称を使用します。

SLH-DSAのhypertree構造

Parameter

treeの「形状」は5つのparameterで定義されます。

1. h：hypertreeの高さ。ひとつの鍵で安全に生成できる署名数は2^hですが、hが大きいほど署名も大きくなります。
2. d：treeの層数。小さいほど署名は小さくなりますが、各層のtreeが高くなり、鍵・署名生成costが指数関数的に増加します。
3. k：FORS treeの数。各treeは安全性に寄与しますが、署名を大きくします。
4. a：FORS treeの高さ。大きいほど同じsecurity levelに必要なtree数は減りますが、鍵・署名生成は複雑になります。
5. w：Winternitz parameter。大きいほどhash chainが少なく署名も短くなりますが、各chainが長くなり、鍵・署名生成に必要なhashが増えます。

SLH-DSAには複数のparameter setがあります。基準にはSLH-DSA-SHA2-128sの(h, d, k, a, w) = (63, 7, 14, 12, 16)を使用し、一定範囲で各parameterを探索して効率的な候補を探します。

要件と制約

1. Securityは128 bit未満にしない（NIST security Level 1）。
2. SLH-DSAの構造は変更せず、algorithm、hash function、addressingなどを維持してparameterだけを変更する。
3. 署名可能回数を2⁴⁰未満にしない（on-chainとL2の両方で実用的）。
4. SLH-DSA-SHA2-128sの7,856バイトより署名を小さくする。

各候補について、署名size、鍵生成cost、署名生成cost、検証cost、署名1バイト当たりの検証costを計算します。CostはSHA-256圧縮関数の呼び出し回数で数え、FIPS 205で認められているPK.seed midstateのcacheを前提とするため、2つのchild nodeのhashingを1回の圧縮として扱います。

探索

h ∈ [40, 50]、d ∈ [2, 25]、k ∈ [6, 24]、a ∈ [8, 20]、w ∈ {16, 32, 256}を探索しました。全層が同じ高さになるためdはhを割り切る必要があり、候補は合計25,935個です。要件を満たす9,182候補から、最も実用的なものを探しました。

詳しくはreportをご覧ください。第1段階では指標ごとの上限・下限を設定し、X_*係数でSLH-DSAに対する相対範囲を表します。たとえば「X_kg = 2.0, X_sg = 0.75」は、鍵生成costをSLH-DSAの2倍以下、署名生成costを25%以上低くするという意味です。5つの制約を順に適用し、どの候補がどの制約を満たさないか確認します。

第2段階では重み付き距離を計算します。各指標をSLH-DSAに対する比率で表し、鍵生成の複雑さや検証costなど、重視する指標にweightを設定します。Explorerは生き残った候補のうち、全指標が0となる理想点への重み付き距離が最小のものを選びます。

結果

SLH-DSAの各指標に近い範囲で最短の署名を探すため、署名sizeへ最も大きなweightを設定し、2つの有望な候補を特定しました。

CはSHA-256圧縮関数の呼び出しcost、Bはバイトを表します。

候補1（C1）は5.7KBで、SLH-DSAより小さく、署名と検証のcostも低くなります。C2は署名生成costが1.37倍になる代わりに、さらに64バイト削減できます。署名の複雑さが重視されない環境では合理的です。

Stateful部分

Stateful部分は用途によって形状が変わるため、分析がより困難です。多くのユーザーは、SHRINCSの中核であるeXtended Merkle Signature Scheme（XMSS）の非対称型UXMSSを選ぶでしょう。署名が最小（324バイト以上、追加署名ごとに16バイト増加）だからです。Lightning Networkやminerでは、同じ鍵から一定sizeで可能な限り多数の署名を生成する必要があるため、XMSSやmulti-tree型のXMSS-MTが適しています。利用機器によって鍵生成の高速化、cache、並列化の効率も異なります。

特定候補を推奨する代わりに、Explorerで直接比較できるようにしました。Stateless部分と同じ方法でSLH-DSAの指標と比較し、指定weightに最も近い候補を検索します。

Explorer

署名候補を分析するオープンソースExplorerを公開しました。制約とweightを設定し、最適な候補を検索できます。

表示する数値はbenchmarkではなく圧縮関数呼び出し回数のmodel値です。候補の順位は正確ですが、実際の処理時間を示すものではありません。SLH-DSAを実行し、Explorerの係数を掛けることで十分近い見積もりを得られます。

耐量子ビットコインにとっての意味

parameterをどう選んでも、ハッシュベース署名を現在のSchnorr署名（64バイト）ほど小さくすることはできません。探索後もSHRINCSのstateful署名は324バイト（約5倍）から始まり、stateless fallbackは約5.7KB（約90倍）です。この差が、stateless経路をbackupだけに使う理由です。

それでもbackupのcostは重要です。候補はSLH-DSAと比べ、fallback署名を約2KB削減し、検証costもさらに28%削減します。

parameterはまだ確定しておらず、特にstateful側はアドレスの用途に依存します。Explorerはオープンソースで公開済みです。ウォレット開発者やprotocol研究者は用途に合う制約とweightを設定し、生き残る候補を確認できます。各表示には共有可能なURLがあり、こちらは本記事の候補を表示します。より説得力のある候補が見つかった場合は、ぜひお知らせください。

• 独自の制約とweightで候補空間を探索する。
• 完全な手法を説明したtechnical reportを読む。
• Delving BitcoinでSHRINCS proposalを読む。

原文：Searching for SHRINCS Parameters