FORS

GBECの解説動画の資料です。
https://goblockchain.network/2026/06/fors/

Transcript

1. FORS(Forest Of Random Subsets)
2. 1 FORS FORS（Forest Of Random Subsets）は、1つの公開鍵/秘密鍵を用いて 数回（Few-Time）の署名が可能なデジタル署名スキーム SPHINCS+（SLH-DSA）の構成要素の１つで実際のメッセージに署名する 【パラメーター】 • k：ツリーの個数 • t：各ツリーの高さ
3. 2 鍵生成 1. マスターシードをランダムに選択 2. シードから擬似ランダム関数PRF(seed, i, j) を使ってk×2t個の秘密鍵を生成 iはツリーのインデックス、jはツリー内のリーフのインデックス 3. 各秘密鍵のハッシュ値をリーフとしてk個のツリーを構築 4. k個のツリーのルートr i を計算 5. k個のルートを連結して ハッシュした値が公開鍵 ※ シードだけあればすべて導出可能
4. 3 署名 メッセージmに対して署名者は、以下の手順で署名を生成する 1. メッセージダイジェストH(m)を計算し 2. 1の結果をtビットずつk個のチャンクに分割する 各ツリーiにtビットのidx[i]が割り当てられる 3. k個の各ツリーに対して以下をピックアップしたのが署名 a. idx[i]に該当するリーフの秘密鍵 b. idx[i] のリーフからルートr i までの 経路で必要な兄弟ノード （マークルパス）
5. 4 署名の検証 メッセージmと署名（k個の秘密鍵とそのマークルパス）を受け取った検証者は、 1. メッセージダイジェストH(m)を計算し 2. 1の結果をtビットずつk個のチャンクに分割する 各ツリーiにtビットのidx[i]が割り当てられる 3. k個の秘密鍵のハッシュ値を計算し、 4. 各ハッシュ値を各ツリーの idx[i]に割り当て、 5. マークルパスを使ってツリーのルートを計算し、 6. 全ルートのハッシュ値を計算し、 公開鍵と一致するか検証する
6. 5 なぜFew-Timeなのか？ Few-Time：何度かなら同じ鍵で署名しても安全だが、ある回数を超えると偽造可能性が無視できなくなる メッセージm、m’について同じFORS鍵で署名した場合 • ツリーiのidx[i] == idx’[i]の場合、新しく漏れる情報はなし • ツリーiのidx[i] != idx’[i]の場合、新しくidx’[i]の秘密鍵が漏れる ※ 同じ秘密鍵の漏洩には問題がない q回署名すると、各ツリーiで開示されたインデックスの集合S i ⊆{0,...2t-1}ができる（|S i | ≦ q） 多数のメッセージm*に対してハッシュを計算し、そのidxがすべて開示済みの集合内にあれば署名の偽造が成功する 計算困難なハッシュの計算量となるようqを設定する必要があり、 • 計算量は約(2t/q)k • 求める安全性をλビットとするとk⋅(t−log 2 q) ≥ λを満たすqを選択すること （128ビットだとパラメーターセットによってq=4〜7くらい）