ハッシュベースのステートレスなデジタル署名スキームSPHINCS+

以前のW-OTS+の記事で少し触れたけど↓

techmedia-think.hatenablog.com

NISTのポスト量子暗号の1つであるハッシュベースのデジタル署名アルゴリズムSPHINCS+は、

（↑の）W-OTS+
ハイパーツリー
FORS（Forest of Random Subsets）

を組み合わせてステートレスな署名スキームを形成している。

ハイパーツリー

ランポート署名やW-OTS+だと、複数のメッセージに対して同じ鍵を使用してしまうと秘密鍵に関する情報が漏洩してしまうため、鍵は1回の署名にしか使えない。

このようなワンタイム署名の場合、署名の度に公開鍵を共有する必要があるが、これを効率的にするために公開鍵をマークルツリーにエンコードする仕組みが提案された。OTSの鍵ペアを複数生成したら（例えば2ⁿ個）、その各OTS公開鍵のハッシュ値をリーフノードとした（高さnの）マークルツリーを構成し、そのマークルルートを公開鍵として共有するというもの。

そして、署名を生成する際は、署名に加えて、OTSの公開鍵および、OTSの公開鍵がマークルツリーに含まれていることを証明するための（n個の）認証パスを提供する。署名を検証する際は、認証パスの有効性を検証した上で、通常のOTSの署名検証を行う。

ここで単純に1つのツリーを構成するのではなく、ハイパーツリーと呼ばれるツリー構造を採用している。ハイパーツリーというのは、複数のレイヤーで構成されるツリーで、各レイヤーは複数のマークルツリーで構成される。下位レイヤーのルートノードが上位レイヤーのリーフノードとリンクする形のツリー構造。各レイヤーの数をdとし、全体のツリーの高さをhすると、各レイヤーのツリーの高さはh/dとなる。たとえば、d = 3、h = 60の場合は、以下のようなツリーが構成される。

    [ルートツリー] --- 最上位レイヤー（高さ20のマークルツリー）
         /  \
        /    \
    [中間ツリー] --- 中間レイヤー（高さ20のマークルツリー）
      /  \
     /    \
[リーフツリー] --- 最下層レイヤー（高さ20のマークルツリー）
   /  \
  /    \
[リーフノード＝W-OTS+の公開鍵のハッシュ] --- 実際の署名に使用される公開鍵

各ツリーのリーフノードがそれぞれW-OTS+の公開鍵のハッシュ値となる。その内、

最下層のツリーのリーフの鍵がSPHINCS+の署名で使われるW-OTS+の鍵で、
中間ツリーのリーフは、下位ツリーのルートノードに署名するのに使われるW-OTS+の鍵

となる。そのため、認証パスには、ツリー上のパスとパス上の下位ツリーのルートに対するW-OTS+署名も含まれる。

↑の前提だと最下層のツリー全体に含まれるW-OTS+公開鍵の数は ${2^{60}}$ 個。もしこれが単一のツリーであれば、鍵生成時にそれだけの鍵を生成して計算するのは現実的には不可能。しかしハイパーツリーであれば、鍵生成時には最上位のツリーのみを構成すれば公開鍵は決められる。そして実際に署名を生成する際に、下位の対象の鍵ツリーを導出すればいい。なお、すべてのツリーの鍵は後述するように、シードデータから決定論的に導出される。

ステートレス性

OTSの場合一度でも使った鍵はもう使えないので、たとえばツリーの左のリーフの鍵から順番に署名に使っていくのであれば、使用済みの鍵のインデックスを記録しておく必要があり、ステートフルな署名スキームになる。使用された鍵を適切に記録し、決して再利用できないようにするというセキュリティのハードルは高く、SPHINCS+ではこれを回避するために署名対象のメッセージダイジェストから署名時に必要なツリー内の鍵を決めることで、ステートレスな署名スキームになっている。

FORS

ハイパーツリーにコミットされるW−OTS+の鍵は、実はメッセージの署名には直接使われない。SPHINCS+では、

署名対象のメッセージからメッセージダイジェストを計算し、
メッセージダイジェストから署名に使用するFORSとW-OTS+の鍵のインデックスを導出し、
FORSの鍵ツリーの該当する鍵を使ってFORS署名を生成し、
そのFORS公開鍵をメッセージとしてハイパーツリー内の該当するW-OTS+の鍵で署名を行う

という二段構成の署名スキームになっている。

FORSは、同じ秘密鍵で限られた数の異なるメッセージに署名できるFew-time署名方式。以下のような単層で横に広がる鍵ツリーを構成する。

↑の図は、高さaのツリーをk個横に並べた鍵ツリー。リーフノードはFORSの秘密鍵のハッシュで、上記のツリーだと全体で ${k * 2^{a}}$ 個の秘密鍵が含まれる。

鍵生成

FORSの秘密鍵は、SPHINCS+の秘密鍵に含まれるシードSK.seed（後述）とツリー内のリーフの位置情報（ADRS*1）を入力として擬似ランダム関数を実行することで決定論的に導出される（sk = PRF(SK.seed, ADRS)）。

FORSの公開鍵は、k個の鍵ツリーのルートハッシュのリスト。ただ、SPHINCS+内で使用する場合、予めFORSの公開鍵を単独で計算することはない。

署名の生成

署名対象のメッセージをMとした場合、FORS署名は以下の手順で生成される。

メッセージMをk個のa-bitの文字列 ${l_0, ..., l_{k-1}}$ に分解し*2、
分解した文字列を0〜2^aの範囲内の数値として解釈し、
k個のツリーから2の数値をインデックスとして該当する秘密鍵をピックアップする。
また3の各秘密鍵が鍵ツリーに含まれていることを証明するためのツリー上の認証パスを計算する。
3と4のk個の秘密鍵とその鍵の認証パスがFORS署名となる（認証パスの数はツリー毎にa個なので、署名はk * (a + 1)個のデータで構成される）。

FORS署名は簡単にいうと、署名対象のメッセージダイジェストの値からk個のツリー内のリーフの位置を決めて、対応する秘密鍵を公開する行為。ランポート署名のように、一度の署名で半分の秘密鍵が露出する署名スキームと比べると、同じFORS公開鍵に対して数回の署名であれば安全であるとされている。

署名から公開鍵を計算

FORSの署名は、他の署名スキームのように明示的にFORSの署名を検証するために使われるのではなく、W-OTS+の鍵での署名対象となるFORSの公開鍵を算出するのに使われる。

k個の秘密鍵と対応する認証パスを使って、k個分の鍵ツリーを復元し、そのルートハッシュのリストがFORSの公開鍵となる。そして、これがW-OTS+鍵で署名されるメッセージとなる。

FORSインスタンス

上記のFORSツリーは、ハイパーツリーの最下層のリーフのW-OTS+の鍵と対になるよう決定論的に構成される。つまりハイパーツリーの高さをh = 60とした場合、割り当てられるFORSツリーの数はハイパーツリーのリーフの数と同様で ${2^{h} = 2^{60}}$ 個になる。

SPHINCS+

以上を踏まえて、SPHINCS+の鍵生成および署名の生成/検証プロトコルは以下のようになる。

パラメーター

SPHINCS+のパラメーターは以下のとおり。

n：セキュリティパラメーターで、ハッシュ関数の出力長（byte単位）
w：W-OTS+のWinternitzパラメーター
h：ハイパーツリーの高さ
d：ハイパーツリーのレイヤー数
k：１つのFORSツリー内の鍵ツリーの数
a：FORSの各鍵ツリーの高さ
t：１つのFORSツリーのリーフの総数（t = k * 2^a）

鍵生成

SPHINCS+の鍵生成は、

最初に以下の３つのランダム値を選択する。
SK.seed：各W-OTS+およびFORSの秘密鍵を導出するのに使われるシード。
PK.seed：公開鍵や鍵ツリーでハッシュ値を計算する際に使われるランダム値で、公開鍵と一緒に公開される。
SK.prf：署名時のメッセージダイジェストおよび鍵インデックスを決定する際に使用されるランダム値。
SK.seedとPK.seedを使って、以下の手順でハイパーツリーの最上位ツリーを構成し、そのツリーのルートを公開鍵PK.rootとする。
SK.seedとツリー内のリーフノードの位置情報（ADRS）を入力として、疑似ランダム関数PRFを使ってW-OTS+秘密鍵を導出し
W-OTS+秘密鍵とPK.seedから各リーフノードに割り当てるW-OTS+公開鍵を計算する。
すべてのW-OTS+公開鍵を導出したら、ルートノードPK.rootを計算する

結果、秘密鍵はSK.seedとSK.prefで構成され、公開鍵はPK.rootとPK.seedで構成される。ただ、署名を生成する際にPK.seedが必要になることから、秘密鍵には公開鍵のコピーも含まれる。

署名の生成

署名対象のメッセージをMとした場合、SPHINCS+の署名は以下の手順で生成される。

擬似ランダム関数 ${PRF_{msg}}$ を使って、ランダマイザー ${R = PRF_{msg}(SK.prf, opt, M)}$ を生成*3
ハッシュ関数を使ってメッセージダイジェスト ${digest = H_{msg}(R, PK.seed, PK.root, M)}$ を計算する。
2のメッセージダイジェストについて、
- 先頭 k * a bitが、FORS署名用のメッセージmd（FORSの署名に必要な秘密鍵のツリー/リーフインデックスを決定）
- 残りのデータでハイパーツリー内のW-OTS+鍵を決定するためのツリー/リーフインデックスを導出
3のmdおよび、SK.seed、PK.seed、ADRSを用いてFORS署名 ${SIG_{fors}}$ を生成
FORS署名 ${SIG_{fors}}$ からFORS公開鍵 ${PK_{fors}}$ を計算
3のツリー/リーフインデックスから署名用のW-OTS+公開鍵に対応する秘密鍵を使ってハイパーツリーのW-OTS+署名 ${SIG_{ht}}$ を生成する。この署名には、リーフからルートまで続くツリーの上位階層のW-OTS+署名も含まれる。
${SIG = R || SIG_{fors} || SIG_{ht}}$ がSPHINCS+の署名データとなる。

digest = Hmsg(R, PK.seed, PK.root, M)
         [最初のk*aビット][残りの部分...]
                 ↑            ↑
           FORS署名用  ハイパーツリー内のツリーとリーフのインデックス

FORSの役割

ハイパーツリーの署名はワンタイム署名のW-OTS+であるため、ハイパーツリー単体だと、ツリー内の鍵のインデックスを導出する際に、同じW-OTS+鍵が導出されると即座に危険になる。そういうことが起きないようにハイパーツリー単体で保証しようとすると、ツリーの高さをh ≈ 128くらいにする必要があり、かなり巨大なツリーを構成しなくてはならない。

FORSと組み合わせると、同じW-OTS+鍵が導出されても、FORSの方は異なる署名が作成され、数回程度であればまだ安全で、その分、ハイパーツリーの高さをh = 63〜66のように低く設定でき実用的なツリーサイズになる。

署名の検証

SPHINCS+の署名検証は、メッセージMと署名SIG、公開鍵PK.rootを入力として、以下を検証する。

SIGからランダマイザーR、 ${SIG_{fors}}$ 、 ${SIG_{ht}}$ をパース。
署名生成時と同じように、メッセージダイジェストを計算し、FORSとハイパーツリー上の鍵を識別するためのデータを導出
FORS署名 ${SIG_{fors}}$ からFORS公開鍵 ${PK_{fors}}$ を計算
${PK_{fors}}$ をメッセージとし公開鍵PK.rootに対し、ハイパーツリーの署名 ${SIG_{ht}}$ を検証する。

以上が、大まかな流れ。冒頭にリンクしてるペーパー内に擬似コードで各アルゴリズムが書かれてるので詳しくはそちらを参照。

パラメーターリスト

SPHINCS+のパラメーター設定毎の、セキュリティレベルおよび署名サイズは以下のとおり：

名称	n	h	d	k	a	w	公開鍵(B)	署名(B)	bitsec	NIST Level
SPHINCS+-128s	16	63	7	14	12	16	32	7,856	133	1
SPHINCS+-128f	16	66	22	33	6	16	32	17,088	128	1
SPHINCS+-192s	24	63	7	17	14	16	48	16,224	193	3
SPHINCS+-192f	24	66	22	33	8	16	48	35,664	194	3
SPHINCS+-256s	32	64	8	22	14	16	64	29,792	255	5
SPHINCS+-256f	32	68	17	35	9	16	64	49,856	255	5

Bitcoinへの導入？

公開鍵のサイズは現状のBitcoinと同サイズなものの、署名のサイズがSPHINCS+-128sでも10倍以上増えるのがネック。Lightning Labsの@roasbeefはBitcoinにSPHINCS+を導入する提案をしてるみたいだけど実際どうなるか？実際にBitcoinへの導入にあたっては、鍵/署名長以外にも以下のような既存のプリミティブがワークするかどうかというのも重要な点になる。

HDウォレット
スクリプトレスマルチシグ
スクリプトレス閾値マルチシグ
サイレントペイメント
集約署名

*1:ADRSは、SPHINCS+内の各暗号計算（ハッシュ関数やPRFの入力になる）に「どこで何の計算をしているか」という一意のコンテキストを与えるアドレス情報。

*2:そのため、SPNIHCS+ではメッセージダイジェスト内の先頭k * a bitをFORS署名の対象メッセージとして渡す

*3:ランダマイザーRがあることで、攻撃者は特定のメッセージに対する鍵インデックスを事前に計算できない。またoptはオプションのランダム性

Develop with pleasure!

福岡でCloudとかBlockchainとか。

ハッシュベースのステートレスなデジタル署名スキームSPHINCS+

ハイパーツリー

ステートレス性

FORS

鍵生成

署名の生成

署名から公開鍵を計算

FORSインスタンス

SPHINCS+

パラメーター

鍵生成

署名の生成

FORSの役割

署名の検証

パラメーターリスト

Bitcoinへの導入？