本稿では、耐量子署名アルゴリズムLMS、XMSS、SLH-DSAの違いを簡単にご紹介します。それぞれの標準仕様は次のとおりです。
- LMS(Leighton-Micali Hash-Based Signatures)
- XMSS(eXtended Merkle Signature Scheme)
- SLH-DSA(Stateless Hash-Based Digital Signature Standard)
これら3つのアルゴリズムの最も重要な類似点は、いずれもハッシュベースの署名方式である点です。ハッシュベースであるため、いずれも量子耐性を持つ署名方式であり、実証済みの実戦で鍛えられたハッシュアルゴリズムのセキュリティ特性を活用しています。いずれもMerkle Treeを用いて、多数のデータ構造インスタンスを単一の公開鍵に結合します。
これらのインスタンスはMerkle Treeのリーフノードを形成し、LMSではWOTS(Winternitz One-Time Signature)と呼ばれ、XMSSではWOTS+と呼ばれます。WOTSは「プレフィックス構成」を採用し、WOTS+はランダムビットマスクを用いた「プレフィックスとビットマスクの構成」を採用することで、より厳しい攻撃モデルを仮定しても安全性が成り立つという保証を実現しています。
XMSSは圧縮に「L-tree」を使用するため、より多くのハッシュ演算が必要となります。LMSには対応する圧縮方式はありません。
パフォーマンスの観点から見ると、LMSは少ないクロックサイクル数で鍵生成、署名、検証を実行できます。XMSSは総じてメモリ消費量が多く、特に署名と検証時に顕著です。
XMSSには相互運用性を損なう様々な理論的な最適化が施されています。LMSはより効率的ですが、その差はごくわずかです。特別な事情でビットマスク構造によるセキュリティ保証が必要な場合にはXMSSを選択すべきですが、そうでなければLMSがよいでしょう。
LMSとXMSSの共通点は、ステートと利用可能な署名数の制限があることです。この制限に達すると、秘密鍵は破棄されなければなりません。ステートは非常に重要です。なぜなら、ステートの管理が不十分だと、署名者がWOTSまたはWOTS+を再利用し、攻撃者が署名を偽造できるようになる可能性があるからです。この深刻な問題を念頭に、SLH-DSAはステートを必要としないことで問題を排除できるように設計されています。SLH-DSAはランダム化アプローチを採用し、衝突の確率について推測を行います。SLH-DSAにおけるWOTSに相当するものは「少数回署名」であることに注意が必要です。
SLH-DSAはステートが不要なため、並列化と分散利用が可能になります。一方、LMSとXMSSでは署名操作が秘密鍵の単一インスタンスに密結合されているため、署名操作は逐次的な処理に限られます。
最後に、最も重要な違いを示します。それは、3つのアルゴリズムすべてがNISTによって標準化・認定されている一方で、CNSA 2.0で使用を承認されているのはLMSとXMSSのみであることです。
これで、LMS、XMSS、SLH-DSAの比較は終了です。とはいえ、これはこれらのアルゴリズムの表面的な部分に触れたに過ぎません。ご質問がございましたら、ぜひ info@wolfssl.jp までお問い合わせください。