ポスト量子暗号におけるハッシュベース暗号について

ポスト量子暗号は量子コンピュータの出現によって従来のRSA暗号や楕円曲線暗号などの公開鍵暗号方式が破られる可能性を念頭に置き、量子コンピュータに対して安全な新たな暗号技術を研究・開発する分野です。その中でもハッシュベース暗号（Hash-Based Cryptography）はハッシュ関数の安全性を基盤とした署名方式として注目を集めています。

ハッシュベース暗号を利用した署名の代表的な方式にはXMSS（eXtended Merkle Signature Scheme）[1]、LMS（Leighton–Micali Signature）[2]、SPHINCS+[3]などがあります。これらはいずれも、量子コンピュータが急速に普及したとしても安全性を維持できると考えられており、NISTのポスト量子暗号標準化プロセスや関連コミュニティでも高い関心が寄せられています。

さらに、ブロックチェーン技術の分野においてもポスト量子暗号を導入する議論が進んでいます。EthereumにおいてはBLS署名の代替としてXMSSを利用した量子耐性の獲得を視野に入れた論文を公開しています[4]。ハッシュベース署名は実装のシンプルさと安全性が相まって、様々な領域においてポスト量子暗号の有力な選択肢の一つとして提案されている経緯となっているようです。

この記事ではハッシュベース暗号について基本的な構造を解説し、ステートレス方式とステートフル方式の違いに触れながら、その後XMSS、LMS、SPHINCS+といった方式を比較しててみたいと思います。

ハッシュベース暗号について

ハッシュベース暗号はハッシュ関数の安全性に基づく暗号方式を指します。量子コンピュータが実用段階に移行してからもハッシュ関数の安全性（衝突耐性や一方向性）は維持されると広く信じられており、RSA暗号や楕円曲線暗号のように、素因数分解や離散対数問題の困難性に頼らない点が特徴です。

代表的なハッシュベース署名構造としては、OTS（One-Time Signature）Merkle Treeを用いたものがあります。OTS自体は、生成されたキーペアを1回のみ署名に利用できる方式であり、キーを再利用すると安全性が著しく低下するという性質を持ちます[5]。このOTSの一度しか使えないという弱点を克服するために、複数のOTSキーをツリー状にまとめ、全体としては複数回署名を行えるようにするMerkle Signature Scheme が登場しました。XMSSやLMSといった方式は、いずれもこのMSSの応用であり、Statefulな署名方式として実装されています。

Merkle Signature Schemeの基本

Merkle署名方式スキームでは多数のOTSキーをリーフとして、その上にハッシュを使って各ノードを構成し、最終的にルートを公開鍵とみなす構造をとります。署名を行う際には、利用するリーフのOTSキーで署名し、そのリーフをルートへとつなぐパスをAuthentication Pathとして受信者に提供します。受信者は、そのAuthentication Pathとリーフの署名を検証することで、正しいルートが導かれるかどうかを確認できます[6]。

Stateful署名

XMSSやLMSのように、ワンタイム署名を繰り返し使用するMerkle署名では、使用済みのOTSキーを再利用しないという状態管理が極めて重要になります。これは秘密鍵が署名のたびに「状態（state）」を持ち、今どのOTSキーが使用済みで、どのOTSキーが未使用なのかをトラッキングする必要があるからです[7]。

• 長所:
  • 署名サイズが比較的コンパクト（SPHINCS+に比べれば小さい）
  • 計算資源が比較的少なくてすむ（パラメータにもよるが、stateless方式よりは軽量になる傾向）
• 短所:
  • 状態管理の複雑さ（鍵を複数回利用した場合のセキュリティリスクの発生）
  • 署名回数に明確な上限がある（リーフの数までしか署名できない）

Stateless署名

SPHINCS+[8]に代表されるStateless署名方式では、秘密鍵に紐づく内部状態を保持しない設計を目指します。すなわち、署名ごとにどのOTSキーを使ったかといった追跡を行う必要がなく、キーペアの管理がシンプルになります[9]。

• 長所:
  • OTSキーの状態管理が不要
  • 署名回数の制限が事実上なくなる
• 短所:
  • 署名サイズが大きい
  • 署名生成や検証に要求される計算量が増大する

代表的なハッシュベース暗号による署名方式

XMSS（eXtended Merkle Signature Scheme）

XMSSはMerkle Signature Schemeを拡張した方式で、署名生成プロセスにおける計算コストを削減する仕組みや、Merkle Treeを段階的に活用するマルチツリー構造を備えており、RFC8391として定義されています。XMSSはStateful署名方式であり、同じOTSキーを2回以上使わないよう状態管理を行う必要があります。EthereumはこのXMSSをBLS署名の代替として利用できる可能性を検討する論文を発表しています[4]。

LMS（Leighton–Micali Signature）

LMSは、Merkle Signature Schemeをさらに汎用化した方式で、RFC8554で標準化されています。XMSSと同様にハッシュツリーを用いたStateful署名方式ですが、以下のような特徴を持ちます[10]。

• 単純化された構造: XMSSに比べると、実装がシンプルになっている
• シード管理の工夫: LMSではOTSキーの生成をシードベースで行い、鍵の一貫した再現性を確保する
• 階層化（HSS: Hierarchical Signature System）: 1階層だけでなく、複数階層を用いることで大量のOTSキーを管理しやすくする

XMSSとの大きな違いは、内部で使われるワンタイム署名のアルゴリズムが異なる点と、署名サイズや計算速度などのトレードオフにおける設計方針にあります。また、LMSも同様にStatefulであるため、鍵の使い回しを管理する必要があります。

SPHINCS+

SPHINCS+は、NISTのポスト量子暗号標準化プロジェクトにおいて標準として選出されたハッシュベース署名方式であり、LMSやXMSSと異なりStatelessである点が特徴です。つまり、同じ秘密鍵を用いて何度でも安全に署名を作成でき、署名回数に上限がありません。

SPHINCS+は、以下のような要素技術を組み合わせて構成されています。

1. Hypertree構造: 複数のMerkleツリーを階層的に結合
2. OTS/FTSの拡張: WOTS+やFORSといったワンタイム署名を組み合わせ、安全性と効率性を両立
3. Randomized Hash: メッセージと署名の組み合わせに依存する形でハッシュを計算し、署名の偽造を難しくする

ただしSPHINCS+はStatelessを実現するために巨大なツリー構造を利用するため、署名サイズや検証の負荷が大きくなるというトレードオフが存在し、XMSSやLMSに比べて計算リソースや署名サイズが大きくなる傾向があります。とはいえ、SPHINCS+の採用が進めば、状態管理の複雑さを排除したハッシュベース署名方式が今後重要になる可能性もあります。

ブロックチェーンとハッシュベース暗号

EthereumにおけるBLS署名の代替としてのXMSS

EthereumのProof of StakeにおけるBeacon Chainでは現在BLS署名が利用されていますが[11]、先日発表された論文においてこれをXMSSベースの署名に置き換えるための技術的検討が行われていました[1]。これは将来的にハードフォークやアップデートを通してポスト量子暗号への移行が必要となる可能性を踏まえたものと言えるでしょう。量子コンピュータが実用化され、従来のBLS署名の方式が破られた場合、コンセンサスプロトコル自体が脅かされるため、BLS署名を耐量子性のある方式に置き換えることが中長期における課題となっています。

EthereumがXMSSを検討している一方でStatelessであるSPHINCS+についても言及されていますが、SPHINCS+はStatelessである分大きな署名サイズと検証コストが発生しやすく複雑なため、論文においてはあえて採用する必要性がなさそうだと考えられているようです。

まとめ

ハッシュベース暗号は、ポスト量子暗号技術の中でも非常に有力な分野の一つです。RSAやECDSAがShorのアルゴリズムのような量子アルゴリズムによって破られる懸念がある一方、ハッシュ関数がGroverのアルゴリズムによって攻撃される場合は十分に大きなハッシュ長を選択すれば安全性を維持できます。

実際、NISTのポスト量子暗号標準化プロジェクトでもハッシュベース署名は有力な候補として存在しており、SPHINCS+が標準として採用されることになりました。XMSSやLMSもRFCや各種標準規格に取り込まれ、実運用を視野に入れた実装が進み、ポスト量子暗号として採用される事例がEthereumを始めとしたブロックチェーンや各システムにおいて増えてくることが想定されるでしょう。

参考文献

[1] XMSS(RFC8391): https://datatracker.ietf.org/doc/html/rfc8391

[2] LMS(RFC8554): https://datatracker.ietf.org/doc/html/rfc8554

[3] SPHINCS+: https://sphincs.org/

[4] Justin Drake, Dmitry Khovratovich, Mikhail Kudinov, Benedikt Wagner, Hash-Based Multi-Signatures for Post-Quantum Ethereum: https://eprint.iacr.org/2025/055

[5] Seyed Mohammadreza Hosseini, Hossein Pilaram, A Comprehensive Review of Post-Quantum Cryptography: Challenges and Advances: https://eprint.iacr.org/2024/1940.pdf

[6] R. C. Merkle, SECRECY, AUTHENTICATION, AND PUBLIC KEY SYSTEMS: https://www.ralphmerkle.com/papers/Thesis1979.pdf

[7] NIST, Recommendation for Stateful Hash-Based Signature Schemes: https://csrc.nist.gov/pubs/sp/800/208/final

[8] NIST, Stateless Hash-Based Digital Signature Standard: https://csrc.nist.gov/pubs/fips/205/final

[9] Stefan Kölbl, Jade Philipoom, A note on SPHINCS+ parameter sets: https://eprint.iacr.org/2022/1725

[10] Panos Kampanakis, Scott Fluhrer, LMS vs XMSS: Comparion of two Hash-Based Signature Standards: https://eprint.iacr.org/2017/349

[11] Ben Edgington, Upgrading Ethereum BLS Digital Signatures: https://eth2book.info/capella/part2/building_blocks/signatures/#bls-digital-signatures