マークル署名方式

ハッシュベースの暗号技術において、マークル署名方式は、マークル木（ハッシュ木とも呼ばれる）とランポート署名方式などのワンタイム署名に基づくデジタル署名方式である。これは1970年代後半にラルフ・マークルによって開発され^{[1] 、}デジタル署名アルゴリズムやRSAなどの従来のデジタル署名の代替となる。NISTは2020年にマークル署名方式の特定のバリアントを承認した。 ^[2]

マークル署名方式の利点は、量子コンピュータによる攻撃に耐性があると考えられていることである。RSAやエルガマルなどの従来の公開鍵アルゴリズムは、効果的な量子コンピュータが構築された場合（ショアのアルゴリズムのため）、安全ではなくなる。しかし、マークル署名方式は、安全なハッシュ関数の存在にのみ依存している。これにより、マークル署名方式は非常に調整可能で、量子コンピュータベースの攻撃に耐性がある。マークル署名は、署名の可能性が有限であるワンタイム署名である。署名ベースの一方向順列と関数に関するモニ・ナオールとモティ・ヤングの研究（およびユニバーサル一方向ハッシュ関数の発明）は、マークルのような署名を完全な署名方式に拡張する方法を提供している。^[3]

マークル署名方式は、1 つの公開鍵を使用して限られた数のメッセージに署名するために使用できます。可能なメッセージの数は 2 の累乗でなければならないため、可能なメッセージの数を と表します。 ${\displaystyle {\text{pub}}}$${\displaystyle N=2^{n}}$

公開鍵を生成する最初のステップは、ワンタイム署名方式（Lamport 署名方式など）の秘密鍵と公開鍵のペアを生成することです。 それぞれについて、公開鍵のハッシュ値が計算されます。 ${\displaystyle {\text{pub}}}$${\displaystyle N}$${\displaystyle (X_{i},Y_{i})}$${\displaystyle 1\leq i\leq 2^{n}}$${\displaystyle h_{i}=H(Y_{i})}$

これらのハッシュ値を使用してハッシュツリーが構築されます。ハッシュ値をリーフとして配置し、再帰的にハッシュしてバイナリ ツリーを形成します。ツリー内のノードを高さ、左右の位置で表します。この場合、ハッシュ値はリーフです。ツリーの各内部ノードの値は、その 2 つの子の連結のハッシュです。たとえば、および です。このようにして、リーフとノードを持つツリーが構築されます。 ${\displaystyle h_{i}}$${\displaystyle 2^{n}}$${\displaystyle a_{i,j}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle h_{i}=a_{0,i}}$${\displaystyle a_{1,0}=H(a_{0,0}||a_{0,1})}$${\displaystyle a_{2,0}=H(a_{1,0}||a_{1,1})}$${\displaystyle 2^{n}}$${\displaystyle 2^{n+1}-1}$

マークル署名方式の秘密鍵は、ペアのセット全体です。この方式の欠点は、秘密鍵のサイズが、送信されるメッセージの数に応じて直線的に増加することです。 ${\displaystyle (X_{i},Y_{i})}$

公開鍵はツリーのルートです。個々の公開鍵は、セキュリティを破ることなく公開できます。ただし、公開鍵には必要ないため、公開鍵のサイズを最小限に抑えるために秘密にしておくことができます。 ${\displaystyle {\text{pub}}}$${\displaystyle a_{n,0}}$${\displaystyle Y_{i}}$

Merkle 署名方式を使用してメッセージに署名するには、署名者はキー ペアを選択し、ワンタイム署名方式を使用してメッセージに署名し、使用されたキー ペアが元のキー ペアの 1 つであること (偽造者によって新しく生成されたものではないこと) を証明する追加情報を追加します。 ${\displaystyle M}$${\displaystyle (X_{i},Y_{i})}$

まず、署名者は、他のメッセージの署名に以前に使用されたことのないペアを選択し、ワンタイム署名方式を使用してメッセージに署名します。その結果、署名と対応する公開鍵が生成されます。 が実際に元の鍵ペアの 1 つであったことをメッセージ検証者に証明するために、署名者は、ツリーのルートで公開鍵を計算するために が使用されたことを検証者が検証できるように、Merkle ツリーの中間ノードを単に含めます。 からルートまでのハッシュ ツリーのパスは、ノード長です。をリーフ、 をルートとして、ノードを呼び出します。 ${\displaystyle (X_{i},Y_{i})}$${\displaystyle {\text{sig}}'}$${\displaystyle Y_{i}}$${\displaystyle (X_{i},Y_{i})}$${\displaystyle h_{i}=a_{0,i}}$${\displaystyle a_{n,0}}$${\displaystyle a_{0,i}}$${\displaystyle n+1}$${\displaystyle A_{0},\ldots ,A_{n}}$${\displaystyle A_{0}=a_{0,i}=H(Y_{i})}$${\displaystyle A_{n}=a_{n,0}={\text{pub}}}$

${\displaystyle A_{i}}$は の子です。検証者が前のノードから次のノードを計算できるようにするには、 のもう 1 つの子、つまり の兄弟ノードを知る必要があります。このノードを と呼ぶので、 となります。したがって、から再構築するにはノードが必要です。認証パスの例を右の図に示します。 ${\displaystyle A_{i+1}}$${\displaystyle A_{i+1}}$${\displaystyle A_{i+1}}$${\displaystyle A_{i}}$${\displaystyle {\text{auth}}_{i}}$${\displaystyle A_{i+1}=H(A_{i}||{\text{auth}}_{i})}$${\displaystyle n}$${\displaystyle {\text{auth}}_{0},\ldots ,{\text{auth}}_{n-1}}$${\displaystyle A_{n}=a_{n,0}={\text{pub}}}$${\displaystyle A_{0}=a_{0,i}}$

ノード、 、およびワンタイム署名は、Merkle 署名方式を使用したの署名を構成します。 ${\displaystyle {\text{auth}}_{0},\ldots ,{\text{auth}}_{n-1}}$${\displaystyle Y_{i}}$${\displaystyle {\text{sig}}'}$${\displaystyle M}$${\displaystyle {\text{sig}}=({\text{sig}}'||Y_{i}||{\text{auth}}_{0}||{\text{auth}}_{1}||\ldots ||{\text{auth}}_{n-1})}$

ワンタイム署名方式として Lamport 署名方式を使用する場合、 には秘密鍵の一部が含まれることに注意してください。 ${\displaystyle {\text{sig}}'}$${\displaystyle X_{i}}$

受信者は公開鍵、メッセージ、署名を知っています。まず、受信者はワンタイム署名公開鍵 を使用してメッセージのワンタイム署名を検証します。が の有効な署名である場合、受信者はワンタイム署名の公開鍵をハッシュして を計算します。 の場合、パスののノードはを使用して計算されます。 がMerkle 署名方式の公開鍵に等しい場合、署名は有効です。 ${\displaystyle {\text{pub}}}$${\displaystyle M}$${\displaystyle {\text{sig}}=({\text{sig}}'||Y_{i}||{\text{auth}}_{0}||{\text{auth}}_{1}||\ldots ||{\text{auth}}_{n-1})}$${\displaystyle {\text{sig}}'}$${\displaystyle M}$${\displaystyle Y_{i}}$${\displaystyle {\text{sig}}'}$${\displaystyle M}$${\displaystyle A_{0}=H(Y_{i})}$${\displaystyle j=1,\ldots ,n-1}$${\displaystyle A_{j}}$${\displaystyle A_{j}=H(A_{j-1}||{\text{auth}}_{j-1})}$${\displaystyle A_{n}}$${\displaystyle {\text{pub}}}$

• E. ダーメン、M. ドリング、E. クリンツェビッチ、J. ブッフマン、LC コロナド ガルサ。 「CMSS - 改良されたマークル署名スキーム」。暗号学の進歩 – Indocrypt 2006、2006。
• E. Klintsevich、K. Okeya、C.Vuillaume、J. Buchmann、E.Dahmen。「実質的に無制限の署名容量を持つ Merkle 署名」。第 5 回応用暗号およびネットワーク セキュリティに関する国際会議 - ACNS07、2007 年。
• S. Micali、M. Jakobsson、T. Leighton、M. Szydlo。「フラクタル マークル ツリーの表現とトラバーサル」。RSA-CT 03、2003

• Merkle ツリーの効率的な使用 -効率的なワンタイム署名方式としての Merkle ツリー + Lamport 署名の本来の目的に関するRSA ラボの説明。
• Adam Langley によるハッシュベース署名と Merkle 署名の紹介。
• David Wong によるハッシュベースの署名に関する 4 部構成のシリーズ。