ハッシュベースの暗号化

ハッシュベース暗号は、ハッシュ関数のセキュリティに基づいた暗号プリミティブの構築に対する総称です。これは、量子耐性暗号の一種として注目されています。

これまで、ハッシュベースの暗号化は、Merkle署名方式などのデジタル署名方式、zk-STARK ^{[1]証明システムなどのゼロ知識証明および計算整合性証明、HashWires [2]}プロトコルを介した発行された資格情報の範囲証明の構築に使用されています。ハッシュベースの署名方式は、 Lamport署名などのワンタイム署名方式とMerkleツリー構造を組み合わせたものです。ワンタイム署名方式のキーは1つのメッセージにしか安全に署名できないため、そのようなキーを多数、1つの大きな構造内に結合することが現実的です。この目的のためにMerkleツリー構造が使用されます。この階層型データ構造では、ハッシュ関数と連結が繰り返し使用されてツリーノードが計算されます。

ハッシュベースの署名方式の1つの考慮事項は、ワンタイム署名方式を使用しているため、限られた数のメッセージにしか安全に署名できないことです。米国国立標準技術研究所（NIST）は、ポスト量子暗号コンペティションのアルゴリズムが少なくとも²⁶⁴の署名を安全にサポートすることを指定しました。^[3]

2022年にNISTは、デジタル署名用に標準化される3つのアルゴリズムの1つとしてSPHINCS+を発表しました。^[4] NISTは、異なる状況に適用可能な拡張マークル署名スキーム（XMSS）とレイトン・ミカリ署名（LMS）^[5]に基づくステートフルハッシュベースの暗号化を2020年に標準化しましたが、使用時に状態を維持する必要があるため、誤用を回避する方法で実装することがより困難になると指摘しました。^{[6] [7] [8]}

2024年にNISTはステートレスハッシュベースのデジタル署名標準を発表しました。^[9]

レスリー・ランポートは1979年にハッシュベースの署名を発明しました。ハッシュベースの署名方式であるXMSS（eXtended Merkle Signature Scheme） ^[10]とSPHINCS ^{[11] [12]は、それぞれ2011年と2015年に導入されました。XMSSは、}ヨハネス・ブッフマンの指導の下、研究者チームによって開発され、Merkleの独創的な方式と2007年の一般化Merkle Signature Scheme（GMSS）の両方に基づいています。^[13] XMSSのマルチツリーバリアントであるXMSS ^MTは、2013年に説明されました。^[14]

ハッシュベースの署名方式は、ワンタイム署名方式を構成要素として使用します。与えられたワンタイム署名キーは、1 つのメッセージに安全に署名するためにのみ使用できます。実際、署名により署名キーの一部が明らかになります。(ハッシュベースの) ワンタイム署名方式のセキュリティは、基礎となるハッシュ関数のセキュリティにのみ依存します。

一般的に使用されているワンタイム署名方式には、 Lamport–Diffie方式、Winternitz方式^[15]、およびその改良版であるW-OTS ^+方式[16]などがあります。独創的なLamport–Diffie方式とは異なり、Winternitz方式とその派生方式では、一度に多くのビットに署名できます。 一度に署名するビット数は、Winternitzパラメータという値によって決まります。 このパラメータの存在により、サイズと速度のトレードオフが生まれます。 Winternitzパラメータの値が大きいと、署名と鍵が短くなりますが、署名と検証が遅くなります。 実際には、このパラメータの一般的な値は16です。

ステートレス ハッシュ ベースの署名の場合、数回署名方式が使用されます。このような方式では、数回キーが複数回使用されると、セキュリティが徐々に低下します。HORST は、数回署名方式の例です。

ハッシュベースの署名方式の中心的な考え方は、多数のワンタイム キー ペアを 1 つの構造に組み合わせて、複数回 (ただし、回数は限られています) 署名する実用的な方法を実現することです。これは、Merkle ツリー構造を使用して行われますが、バリエーションも可能です。1 つの公開キーと 1 つの秘密キーは、基礎となるワンタイム スキームの多数の公開キーと秘密キーから作成されます。グローバル公開キーは、Merkle ツリーの最上位にある単一のノードです。その値は、選択されたハッシュ関数の出力であるため、一般的な公開キーのサイズは 32 バイトです。このグローバル公開キーの有効性は、ツリー ノードのシーケンスを使用して、特定のワンタイム公開キーの有効性と関連しています。このシーケンスは認証パスと呼ばれます。これは署名の一部として保存され、検証者が 2 つの公開キー間のノード パスを再構築できるようにします。

グローバル秘密鍵は、通常、疑似乱数ジェネレータを使用して処理されます。シード値を保存するだけで十分です。ジェネレータを使用して、シード値からワンタイム秘密鍵が連続的に生成されます。このアプローチでは、グローバル秘密鍵も非常に小さく、通常は 32 バイトです。

ツリートラバーサルの問題は、署名のパフォーマンスにとって重要です。ますます効率的なアプローチが導入され、署名時間が大幅に短縮されました。

ハッシュベースの署名方式の中には、複数の層のツリーを使用するものがあり、署名は大きくなりますが、署名速度は速くなります。このような方式では、メッセージの署名には最下層のツリーのみが使用され、他のすべてのツリーは下位のツリーのルート値に署名します。

Naor-Yungの研究^[17]は、Merkle型ファミリーの限られた時間署名を無制限の（通常の）署名スキームに変換するパターンを示しています。

ハッシュベースの署名方式は、基礎となるハッシュ関数に関するセキュリティの仮定に依存しますが、これらの仮定を満たすハッシュ関数であればどれでも使用できます。その結果、適切なハッシュ関数ごとに、対応するハッシュベースの署名方式が異なります。特定のハッシュ関数が安全でなくなった場合でも、別の安全なハッシュ関数に置き換えるだけで、検討中のハッシュベースの署名方式の安全なインスタンス化を実現できます。一部のハッシュベースの署名方式 (疑似ランダム キー生成を使用する XMSS など) は前方安全性が高く、秘密キーが侵害されても以前の署名は有効なままです。

セキュリティの仮定が最小限であることも、ハッシュベースの署名方式のもう 1 つの特徴です。一般に、これらの方式では、方式全体のセキュリティを保証するために、安全な (たとえば、2 番目の原像耐性という意味での) 暗号ハッシュ関数のみが必要です。この種の仮定は、あらゆるデジタル署名方式に必要ですが、他の署名方式では追加のセキュリティの仮定が必要ですが、ここではそうではありません。

ハッシュベースの署名方式は、基盤となるワンタイム署名方式に依存しているため、安全に署名できるメッセージ数は固定数に限られます。Merkle 方式と XMSS 方式の場合、 Merkle ツリーの合計の高さに応じて、安全に署名できるメッセージ数は最大になります。 ${\displaystyle 2^{h}}$${\displaystyle h}$

Merkleの最初の方式以来、パフォーマンスが改善されたハッシュベースの署名方式が数多く導入されています。最近のものには、XMSS、Leighton–Micali (LMS)、SPHINCS、BPQS方式などがあります。ハッシュベースの署名方式のほとんどはステートフルです。つまり、従来のデジタル署名方式とは異なり、署名には秘密鍵の更新が必要です。ステートフルなハッシュベースの署名方式では、署名には、使用したワンタイムキーの状態を保持し、再利用されないようにする必要があります。XMSS、LMS、BPQS ^[18]方式はステートフルですが、SPHINCS方式はステートレスです。SPHINCS署名は、XMSS署名やLMS署名よりも大きくなります。BPQSは、ブロックチェーンシステム用に特別に設計されています。WOTS+ワンタイム署名方式に加えて、^[16] SPHINCSはHORSTと呼ばれる数回（ハッシュベース）の署名方式も使用します。 HORSTは、古い数回署名方式であるHORS（Hash to Obtain Random Subset）を改良したものである。^[19]

ステートフルハッシュベースのスキームXMSSとXMSS ^MTは、 RFC 8391（XMSS：拡張マークル署名スキーム）で指定されています。 ^[20] Leighton-Micaliハッシュベース署名は、RFC 8554で指定されています。 ^[5]文献では、ステートフルスキームによってもたらされる懸念を軽減する実用的な改善が提案されています。^{[21]これらのスキームに適したハッシュ関数には、} SHA-2、SHA-3、BLAKEなどがあります。

XMSS、GMSS、およびSPHINCS方式は、Java Bouncy Castle暗号化APIで使用できます。^[22] LMS ^{[23]およびXMSS方式は、} wolfSSL暗号化APIで使用できます。 ^[24] SPHINCSは、SUPERCOPベンチマークツールキットに実装されています。^[25] XMSS RFCの最適化された^[26]および最適化されていない^{[27]参照実装が存在します。LMS方式は、インターネットドラフトに従ってPython [28]}およびC ^[29]で実装されています。

• T. Lange. 「ハッシュベース署名」。暗号化とセキュリティの百科事典、Springer US、2011年。[2]
• FT Leighton、S. Micali。「1つの安全なハッシュ関数に基づく、証明可能な高速かつ安全な大規模デジタル署名方式」。米国特許5,432,852、[3] 1995年。
• G. ベッカー「マークル署名方式、マークル木とその暗号解析」、ドイツ、ルール大学ボッフムでの「ポスト量子暗号学」セミナー、2008年。[4]
• E. ダーメン、M. ドリング、E. クリンツェビッチ、J. ブッフマン、LC コロナド ガルシア。 「CMSS — 改良されたマークル署名スキーム」。暗号学の進歩 – Indocrypt 2006。[5]
• R. マークル「秘密、認証、公開鍵システム / 認定デジタル署名」。スタンフォード大学電気工学部博士論文、1979年。[6] 2018年8月14日、Wayback Machineにアーカイブ
• S. Micali、M. Jakobsson、T. Leighton、M. Szydlo。「フラクタル マークル ツリーの表現とトラバーサル」。RSA-CT 03。[7]
• P. Kampanakis、S. Fluhrer。「LMS vs XMSS: ステートフルハッシュベース署名提案標準の比較」。Cryptology ePrint Archive、レポート 2017/349。[8]
• D. Naor、A. Shenhav、A. Wool。「ワンタイム署名の再考：フラクタルマークルツリートラバーサルを使用した実用的な高速署名」。イスラエルにおけるIEEE第24回電気電子技術者会議、2006年。[9] 2018年2月5日にWayback Machineにアーカイブされました。

• [10] ハッシュベースの署名方式に関する文献のコメント付きリスト。
• [11] 別の参考文献リスト（コメントなし）。