前回までの記事(1)~(3)を踏まえて,実際にの署名方式を見ていきます。

PQCrypto耐量子として推奨される署名方式についてリリースしています。 二つの耐量子アルゴリズムは,XMSSSPHINCSです。 以下,引用です。

  1. Public-key signatures

    Similar to encryption, currently used signatures are based on problems that become easy to solve with a quantum computer. Signatures use cryptographic hash functions in order to hash the message and then sign the hash. Hash-based signatures use nothing but such a hash function and thus assume the minimum requirement necessary to build signatures. PQCRYPTO recommends the following two hash-based systems to achieve \(2^{128}\) post-quantum security:

  • XMSS [7] with any of the parameters specified in [11]. XMSS requires maintaining a state.

  • SPHINCS-256 [5]. SPHINCS is stateless.

Example of another choice under evaluation: the HFEv- [15] multivariate-quadratic signature system.

XMSSはステートフル署名方式,SPHINCSはステートレス署名方式です。

XMSS

XMSS(eXtended Merkle Signature Scheme)は2011年に発表され,インターネット上のドラフトは2015年にできました。

いくつかの点を除いて,Merkle木のような構成になっています。XMSS木には,親ノードがハッシングされる前に子ノードへXORされるマスクがあります。全てのノードでマスクは異なります。

二つ目の特徴は,XMSS木の葉がOTS署名公開鍵のハッシュではなく,L木と呼ばれる別の木のルートであることです。

L木の葉の中には,WOTS+公開鍵の要素が格納されています。 WOTS+公開鍵をなぜ木に格納するのかはHuelsingが論文内で書いてあるので引用します。

The tree is not used to store a WOTS public key but to hash it in a way that we can prove that a second-preimage resistant hash function suffices (instead of a collision resistant one).
意訳:この木はWOTS公開鍵を格納するために使用されるのではなく,(衝突耐性の代わりに)第二原像攻撃耐性のあるハッシュ関数が十分であることを証明できるようにハッシングするために使われます。

SPHINCS

SPHINCSはステートフル署名です。PHINCSは多くの木で構成されています。

  • 各ノードは一つ前のノードとレベルビットマスクを連結しXORしたハッシュです。

  • 公開鍵はビットマスクされたルートハッシュです。

  • 木の葉は,WOTS+ L木の圧縮された公開鍵です。

ビットマスク部分は,SPHINCSのハッシュ木(レベルごとに一意のマスク)のように見える点を除いて,前述のXMSS L-treeと同じです。

1つのWOTSを含む葉は,もう一つの木に署名することが可能です。 4つのSPHINCS木の2番目のレイヤーは,WOTS+公開鍵を自分の葉に含んでいます。 最初に設定したパラメータの通りに進んでいき,最後のレイヤー0に到達すると,WOTS+署名はほかのSPHINCS木ではなくて,HORS木に署名します。

HORST木やHORS木はL木と同様ですが,今回はWOTSの代わりにHORS FTSが含まれています。もし同じHORS鍵を使ってメッセージに署名しても問題ないので,それらを使ってメッセージに署名し,これが署名方式のセキュリティを向上させます。

以下は,WOTS+ L木のイメージ図(次のSPHINCS木への署名としてそれらを描くもの)で,メッセージへのパスを一つだけ示したものです。SPHINCSの論文から引用します。

メッセージMに署名するときには,最初にMと"ランダムな"インデックスで"ランダム化された"ハッシュを作成します(PHINCSのすべてが確定的にPRFで計算されるので,ランダムを強調して書いています)。インデックスは,Mのランダム化されたハッシュに署名するために,HORSTが何を選択するかを示しています。これがステートフルではなくなる方法です:メッセージに従って決定論的にインデックスを選ぶことによります。同じメッセージに再度署名する場合は,同じHORSTを使用する必要があります。異なる2つのメッセージに署名するには,2つの異なるHORSTを使用する必要があります。