ポスト量子暗号とその種類
ブロックチェーンにおいてはハッシュ関数や楕円曲線暗号(ECDSA)などのプリミティブな暗号が利用されていますが、量子コンピュータの発展に伴いポスト量子暗号(PQC, Post-Quantum Cryptography)の導入がコミュニティでも議論されています。Ethereumで2024年末に発表されたBeam Chainではゼロ知識証明の導入に加えて量子耐性の導入についても改めて言及されました[1]。
この記事ではブロックチェーンに限らずセキュリティ一般について広く影響を与えることが言及されている量子コンピュータに対しての耐性を持つ、ポスト量子暗号についてまとめます。
量子コンピュータとポスト量子暗号
量子コンピュータでは古典コンピュータでは現実的な時間での計算が難しい問題を高速に解くためのアルゴリズムが提案され、かつ量子ビットの数も増加しています（とはいえ量子誤り耐性を持つ量子コンピュータの実現は100万量子ビットが必要[2]と言われており、その段階へはまだ達していません）。
量子コンピュータの代表的なアルゴリズムであるShorのアルゴリズム[3]は、古典コンピュータでは現実的な時間での解答を出すことが困難とされてきた大きな整数の素因数分解や離散対数問題を多項式時間で計算できることが理論的に示されています。現在広く用いられているRSA暗号や楕円曲線暗号は、素因数分解や離散対数問題の困難性を安全性の根拠としていますが、量子コンピュータが大規模な量子ビットによる量子謝り耐性を実現した場合、これらの暗号方式は短時間で解読される可能性が顕在化します。
こうした量子コンピュータの脅威に対抗するために研究が進められているのが、ポスト量子暗号で、量子コンピュータと古典コンピュータの両方に対して安全な暗号を目指してNISTによる標準化が進められています。
ポスト量子暗号はいくつかのアプローチがあり、それぞれが特有の長所と短所を持っています。この記事ではポスト量子暗号の種類とその概要についてまとめます。
ハッシュベース暗号
ポスト量子暗号の一つのアプローチとして、ハッシュ関数の困難性に基づくハッシュ(Hash-based)暗号があります。これは従来からあるハッシュ関数を暗号の安全性の基盤として用いるもので、一方向性と衝突困難性の性質を利用しています。
代表例として挙げられるのはXMSS（Extended Merkle Signature Scheme）[4]やSPHINCS+[5]といったデジタル署名方式です。これらは、ハッシュ関数を繰り返し適用してツリー構造（Merkle Tree）を構築し、その構造を利用して安全性を高める仕組みを持っています。一方で、ハッシュベースの署名方式は鍵や署名サイズが比較的大きくなりがちという課題があります。特に巨大なツリー構造を管理するコストが発生しやすい点は実運用上の大きな懸念点です。しかしながらハッシュ関数自体の安全性は比較的よく研究されており、量子コンピュータが実用化した後でもハッシュ関数を破るアルゴリズムとしてGroverのアルゴリズム[6]が挙げられているものの、強度を十分に確保する手段としてハッシュビット長を2倍に伸ばすなどの対策が可能です。こうした特性から、ハッシュベースの暗号は堅牢性に優れ、実装も比較的シンプルであるため、ポスト量子暗号候補としての存在感は大きいといえます。
格子ベース暗号
ポスト量子暗号の主要な分野として、格子ベース(Lattice-based)暗号が挙げられます。これはLearning With Errors(LWE)問題[7]やShort Integer Solutions(SIS)問題[8]が非常に困難であるという数学的性質に基づいています。格子ベース暗号には、秘密鍵を埋め込んだ格子上の情報からその秘密鍵を導き出すことが極めて難しいという構造上の強みがあります。
格子暗号の例としては、NISTの標準化として発表されている鍵共有暗号化方式のML-KEMやデジタル署名方式のML-DSAなどが挙げられます。これらは、現時点で非常に高い耐量子性を示すとともに、計算効率や実装の容易性にも優れ、従来のRSAや楕円曲線暗号と比較しても、実運用に耐え得るパフォーマンスを示すと評価されています。
ただし格子ベース暗号にも課題はあり、鍵サイズや暗号文サイズの増大が避けられない場合があること、実装上の微妙なパラメータ選択などで安全性が左右される可能性があることなどが挙げられます。それでも大量のメモリを確保できる近年のコンピューティング環境では、格子ベース暗号が現実的なオプションとして非常に有望視されており、ポスト量子暗号の中心的な技術のひとつとなっています。
符号ベース暗号
符号ベース(Code-based)暗号は、誤り訂正符号（Error-Correcting Codes, ECC）を利用する暗号方式です。代表的なアルゴリズムとしてはMcEliece暗号[9]やNiederreiter暗号[10]が挙げられます。これらは1970年代から研究されており、歴史が古いという意味でもよく知られています。
符号ベース暗号の特長は、その安全性が数学的に証明された「ランダム線形符号の復号問題」に基づいており、大規模な量子コンピュータでも実用的な時間内での解読は困難だと考えられている点です。McEliece暗号では、誤り訂正符号の生成行列に秘密の変換操作を施すことで公開鍵を作り、復号時には秘密鍵に相当する誤り訂正アルゴリズムを使って正しいメッセージを復元します。この仕組みにより、第三者が復号処理を試みても、公開された符号がランダムな符号に見えるため、効率的な復号は不可能となり、量子コンピュータをもってしても実用的な時間での解読は困難だと考えられています。
一方で、符号ベース暗号では公開鍵のサイズが非常に大きくなるという実用上の課題があります。実際の通信やストレージへの負担が増大するため、この課題に対してはBIKEやHQCなど、より効率的な新しい方式が提案されています。それでも長年にわたる研究の蓄積による安全性への信頼と、量子コンピュータによる攻撃への耐性から、符号ベース暗号は次世代の暗号基盤の重要候補の一つとして認識されています。
多変数多項式ベース暗号
多変数多項式暗号(Multivariate Cryptography)は、多変数多項式の連立方程式を解く問題の難しさに基づいて設計される暗号です。例えばUOV（Unbalanced Oil and Vinegar）[11]と呼ばれる方式が知られており、これは多変数の非線形な多項式を使ってデジタル署名を行う手法として提案されています。
多変数暗号が注目される主な理由として、従来の公開鍵暗号方式と比較して非常にコンパクトな署名サイズを実現できる点が挙げられます。この特性は、IoTデバイスやスマートカードなどの計算資源が制限された環境での実装に特に適しています。一方で、公開鍵サイズが比較的大きくなることや、方式によっては構造的な脆弱性が発見されるなどの課題も存在します。
多変数多項式に基づく暗号システムは、その数学的構造の複雑さゆえに、安全性と実装効率性の両立が従来から課題とされてきました。しかし、近年の研究では、より堅牢なパラメータ選択手法の確立や、新しい設計パラダイムの提案など、着実な進展が見られています。特に、量子コンピュータへの耐性を持つポスト量子暗号の有力候補の一つとして、さらなる研究開発が期待されています。
同種写像ベース暗号
同種写像(igogeny)とは、2つの楕円曲線間を結ぶ同種写像を指します。同種写像をベースとした暗号の代表例としてSIDH（Supersingular Isogeny Diffie-Hellman key exchange）[12]やCSIDH（Commutative SIDH）[13]などが知られており、従来の楕円曲線暗号とは異なる数学的枠組みで安全性が検討されています。
同種写像暗号は、与えられた2つの楕円曲線間の同種写像を見つける問題が量子コンピュータでも解くことが非常に困難とされている点を利用しています。SIDHは鍵交換プロトコルとしての適用が期待されてきましたが、2022年にCastryckとDecruによってSIDHに対する実用的な攻撃手法が報告され、大きな話題となりました。この攻撃によってSIDHの安全性は破られましたが、CSIDHや最近開発されたSQISignをはじめとする他の同種写像暗号の研究は続いており、今後も量子耐性暗号の有力な選択肢になり得ると考えられます。
NISTの標準化プロジェクト
ポスト量子暗号に対してはNIST(National Institute of Standards and Technology）が中心となって標準化を進めています。NISTは2016年からポスト量子暗号についてのRequest for Commentsを求め、世界中の研究者や暗号の専門家から多くの提案を受け取りました。これらの候補を数年かけてレビューしていますが、2024年8月に以下を3つのポスト量子暗号の標準として発表しています[15] 。
- ML-KEM(FIPS 203)
CRYSTALS-KYBERを基にした量子耐性の鍵カプセル化方式で、安全な共有鍵の生成と鍵交換を実現します。 - ML-DSA(FIPS 204)
CRYSTALS-Dilithiumを基にした格子ベース署名方式で、安全なデータ認証と否認防止を提供します。 - SLH-DSA(FIPS 205)
SPHINCS+に基づくステートレスハッシュ署名方式で、データの改ざん防止や否認防止を実現します。
NISTの標準化プロセスは、最終的に新しい暗号標準を策定し、政府機関や民間企業が安全な通信を行うための指針として利用されることが期待されます。将来的には、インターネット上での暗号通信やあらゆるセキュリティ機能にこれらのPQC方式が組み込まれることになるでしょう。
まとめ
ポスト量子暗号は量子コンピュータの出現による従来の暗号方式の危殆化に対応するために開発された暗号技術です。ハッシュベース暗号、格子ベース暗号、符号ベース暗号、多変数多項式ベース暗号、同種写像ベース暗号など様々な数学的基盤に基づく方式が提案されており、それぞれが独自の利点と課題を持っています。
NISTの標準化プロジェクトによって選定された暗号方式は、今後のポスト量子暗号の中核となることが期待されています。しかし、これらのアルゴリズムの実装と普及には効率性の改善やセキュリティの確保、既存システムからの移行など、多くの課題が残されています。
量子コンピュータの実用化時期については不確実性が残るものの、暗号システムの移行には相当な時間と労力が必要となることから、早期からの準備が重要です。
参考文献
[1] Justin Drake, About Beam chain: https://www.youtube.com/live/rGE_RDumZGg?si=6DUeed_oN6w5QaPS&t=7196
[2] Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer, Elucidating Reaction Mechanisms on Quantum Computers: https://arxiv.org/pdf/1605.03590
[3]P.W. Shor, Algorithms for quantum computation: discrete logarithms and factoring: https://ieeexplore.ieee.org/abstract/document/36570
[4] Johannes Buchmann, Erik Dahmen, and Andreas Hülsing, XMSS - A Practical Forward Secure Signature Scheme based on Minimal Security Assumptions: https://eprint.iacr.org/2011/484
[5] Daniel J. Bernstein, Andreas Hülsing, Stefan Kölbl, Ruben Niederhagen, Joost Rijneveld, and Peter Schwabe, The SPHINCS+ Signature Framework: https://eprint.iacr.org/2019/1086
[6] Lov K. Grover, A fast quantum mechanical algorithm for database search: https://dl.acm.org/doi/10.1145/237814.237866
[7] Oded Regev, On lattices, learning with errors, random linear codes, and cryptography: https://dl.acm.org/doi/10.1145/1568318.156832
[8] M. Ajtai, Generating hard instances of lattice problems: https://dl.acm.org/doi/10.1145/237814.237838
[9] R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory: https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF
[10] H. Niederreiter, Knapsack-type cryptosystems and algebraic coding theory: https://cir.nii.ac.jp/crid/1571980076566605568
[11] Aviad Kipnis, Jacques Patarin & Louis Goubin, Unbalanced Oil and Vinegar Signature Schemes: https://link.springer.com/chapter/10.1007/3-540-48910-X_15
[12] SIKE – Supersingular Isogeny Key Encapsulation: https://sike.org/
[13] Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes, CSIDH: An Efficient Post-Quantum Commutative Group Action: https://eprint.iacr.org/2018/383
[14] SIKE Foreword and Postscript: https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/round-4/submissions/sike-team-note-insecure.pdf
[15] NIST Releases First 3 Finalized Post-Quantum Encryption Standards: https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards