SLH-DSA (SPHINCS+)

GBECの解説動画の資料です。
https://goblockchain.network/2026/09/slh-dsa/

Transcript

1. SLH-DSA（SPHINCS+）
2. SLH−DSA（SHIPNCS+） 1 ハッシュ関数だけが安全性の根拠 格子・符号・多変数多項式といった新しい数学的仮定を一切使わない。 第二原像耐性など、既存のハッシュ関数に対する枯れた仮定のみに依存する FIPS 205 2024年に標準化 2 ステートレス 署名のたびに使用済みインデックスを記録・同期する必要がない。 鍵のバックアップや複数マシンへの複製をしても鍵が壊れない 32 B 公開鍵サイズ（128s） 3 既存3つの署名スキームの組み合わせ W-OTS+ （ワンタイム）→ XMSS / Hyper Tree （d層のマークルツリー）に、 FORS（Few-Time） を重ねた構成 7,856 B 署名サイズ（128s） 1
3. 参考 • W-OTS+ https://goblockchain.network/2026/03/wots-plus/ • FORS(Forest Of Random Subsets) https://goblockchain.network/2026/06/fors/ • XMSS/Hyper Tree https://goblockchain.network/2026/08/Hyper-Tree/ 2
4. 全体構造：Hyper Tree＋FORS 公開鍵 = このツリーのルート PK.root • SLH-DSA は Hyper Tree（HT） と FORS の2段構え XMSS ツリー（レイヤー d−1） ▪ HT最下層のリーフ（W-OTS+鍵）が「FORS公開鍵」に署名する鍵 ▪ FORS鍵が実際のメッセージダイジェストに署名する鍵 W-OTS+ で署名 ⋮ 中間レイヤー ⋮ W-OTS+ で署名 XMSS ツリー（レイヤー 0） • なぜ FORS を挟むのか ▪ HTのリーフを直接メッセージ署名に使うと、インデックスの衝突が そのままW-OTS+鍵の再利用になり即座に破綻する ▪ FORSは数回の再利用に耐えるので、 インデックスを擬似ランダムに選ぶ（＝衝突を許す）設計が成立する • 公開鍵は最上層XMSSツリーのルート PK.root と PK.seed だけ ▪ 2 h 個の鍵ペアが、32 byte の公開鍵に圧縮される W-OTS+ で署名 FORS 鍵（Few-Time） 1回の署名で計算するのは、この縦一列の経路だけ。 FORS で署名 他の 2h − 1 個の鍵は、必要になるまで存在しない メッセージ M のダイジェスト 3
5. 鍵生成 ランダムに生成 秘密鍵 SK … 4n byte SK.seed すべてのW-OTS+鍵・FORS鍵を擬似ランダム関数 （PRF）で決定論的に導出するためのシード SK.prf 署名時のランダマイザ R を生成するためのシード PK.seed ハッシュのドメイン分離に使う「公開シード」 PK.root 最上層XMSSツリーのルート 公開鍵 PK … 2n byte PK.seed と PK.root の2つだけ 秘密鍵から公開部分を取り出したもの 64 B / 32 B SLH-DSA-SHA2-128s の 秘密鍵 / 公開鍵 鍵生成で実際に計算するのは、最上層のツリーだけ • 必要なのは 2 h′ 個のW-OTS+鍵だけ（h′=9 なら 512 個）。 下位層はSK.seed から決定論的に導出できるので署名時にオンデマンドに計算可能 • 2 h 回署名できる鍵を、512 回程度のリーフ計算で作れる。これが Hyper Tree のメリット 4
6. 署名の生成 ダイジェストとインデックスの決定 1 ランダマイザ Rを計算 2 メッセージダイジェストを計算 R = PRF msg (SK.prf, opt_rand, M) digest = H msg (R, PK.seed, PK.root, M) opt_rand を PK.seed に R と公開鍵を混ぜるので 固定すれば決定論的署名になる 鍵ごと・署名ごとに値が変わる 3 3つに切り分ける digest から md / idx_tree / idx_leaf を取り出し、使う鍵の位置を決める digest（m byte）の内訳 — SLH-DSA-SHA2-128s なら m = 30 byte md idx_tree idx_leaf FORSで署名する部分 ⌈k·a/8⌉ = 21 byte 最下層のどのXMSSツリーか ⌈(h−h′)/8⌉ = 7 byte ツリー内のどのリーフか ⌈h′/8⌉ = 2 byte ここが「ステートレス」の核心：どの鍵を使うかをカウンタではなく「メッセージと R のハッシュ」で決めるため、 署名者は状態を持たなくてよい 5
7. 署名の生成 FORS→Hyper Tree 1 FORS鍵を導出 (idx_tree, idx_leaf) が指す FORS鍵 を SK.seed から導出 2 FORS署名 3 md に対するFORS 署名 SIG_FORS を生成 （k個の秘密鍵＋各マークルパス） PK_FORS を復元 4 SIG_FORS から FORS公開鍵 を 計算して取り出す HT署名 PK_FORS を対象に HTの署名 SIG_HT を生成 （d層分のW-OTS+ 署名＋パス） 署名 SIG = R ‖ SIG_FORS ‖ SIG_HT — SLH-DSA-SHA2-128s の 7,856 byte の内訳 R SIG_FORS SIG_HT n = 16 B k(a+1)·n = 14×13×16 = 2,912 B (h + d·len)·n = (63 + 7×35)×16 = 4,928 B 署名サイズ ＝ ( 1 + k·(a+1) + h + d·len ) · n byte ※ len = 2n + 3（w = 16） 6
8. 署名の検証 検証者が持つのは M、SIG = (R, SIG_FORS, SIG_HT) 、PK = (PK.seed, PK.root) 1 digest = H_msg(R, PK.seed, PK.root, M) を再計算し、 md / idx_tree / idx_leaf を復元する 2 md と SIG_FORS から FORS公開鍵 PK_FORS を計算する （k個の値をハッシュ→マークルパスで各ルート→連結してハッシュ） だけ 検証は 「ハッシュ計算の再実行」だけ • 秘密情報も乱数も不要 • 完全に決定論的で、 3 PK_FORS を署名対象として、SIG_HT の最下層のW-OTS+署名から公開鍵を復元し、マーク ルパスでレイヤー0のルートを算出する 誰でも同じ結果を再現できる • 検証コストは署名生成よりずっと軽い • 必要な計算はハッシュ関数の呼び出しのみ。 4 算出したルートを上位層の署名対象として、同じ計算をレイヤーd−1 まで繰り返す 剰余演算も多倍長整数も出てこない 最終的に得られたルートが PK.root と一致すれば、署名は有効 7
9. どうしてステートレスにできるのか？ XMSS 単体：ステートフル SLH-DSA：ステートレス • 未使用の idx を選んで署名する • idx をメッセージと R から擬似ランダムに決める • 「どの idx を使ったか」を永続的に記録・同期する必要がある • 状態管理は不要になるが、 • 同じ idx を2回使うと W-OTS+ のワンタイム性が破れ、 秘密鍵の一部が漏れる • バックアップからの復元や複数マシン運用が事故のもとになる 同じ FORS鍵が複数回選ばれることは避けられない • だから最下層をワンタイムの W-OTS+ ではなく、 Few-Time の FORS にしている • 鍵の複製・バックアップをしても壊れない 安全性はどう担保されるか • 攻撃者は多数の署名を集め、ある1つのFORS鍵について「開示済みインデックスだけで構成できるメッセージ」を探す • FORSの k 本のツリーすべてで開示済み idx を引く確率が無視できるよう、 k・a・h を設定する（ 2 64 回署名しても目標安全性を割らない） （k: FORSツリーの個数、 a: 各FORSツリーの高さ） • ランダマイザ R により同じメッセージでも idx が変わり得るため、攻撃者が特定のFORS鍵に署名を集中させられない 8
10. パラメーターセット 「*」は SHA2 または SHAKE。ハッシュ族2種 × 安全性3段階 × s/f の計12セット パラメーターセット n h d h′ a k 公開鍵 秘密鍵 署名サイズ SLH-DSA-*-128s 16 63 7 9 12 14 32 B 64 B 7,856 B SLH-DSA-*-128f 16 66 22 3 6 33 32 B 64 B 17,088 B SLH-DSA-*-192s 24 63 7 9 14 17 48 B 96 B 16,224 B SLH-DSA-*-192f 24 66 22 3 8 33 48 B 96 B 35,664 B SLH-DSA-*-256s 32 64 8 8 14 22 64 B 128 B 29,792 B SLH-DSA-*-256f 32 68 17 4 9 35 64 B 128 B 49,856 B s（small signature） f（fast signing） 署名は小さいが、署名生成が遅い 署名生成は速いが、署名が大きい • d が小さく h′ が大きい → 1層あたりのツリーが大きく、 署名時のオンデマンド計算が重い • d が大きく h′ が小さい → 1本あたりのツリーが小さく、 計算が軽い • その代わりHT署名に含まれる層数 d が少なく、 署名が短くなる • その代わり層数 d の分だけW-OTS+署名が積み上がり、 署名が2倍以上になる 9