ログイン/ 登録

ゲルハルト・コードに量子の危機？Gコードをめぐる学術的騒動についての記事

2024/04/24 20:30

従う

Quantum Security Threats to Blockchain and Response

2024年3月10日、イーサリアムの共同創設者であるヴィタリック・ブテリン（Vitalik Buterin）氏は、イーサリアム・リサーチ（Ethereum Research）に新しい記事「How to hard-fork to save most user's funds in a quantum emergency」[1]を掲載した。フォーラム（ethresear.ch）の最新記事「How to hard-fork to save most user's funds in a quantum emergency」[1]で、イーサリアムのエコシステムに対する量子コンピューティング攻撃の脅威は、レジリエントなフォーク戦略とアンチ量子暗号によってユーザーの資金を守ることができるとしている。資金を安全に保つことができるとしています。

ブロックチェーンに対する量子セキュリティの脅威とは一体何なのでしょうか？

量子コンピューティング [2] 新しいコンピューティングモデルの計算のための量子情報ユニットを調整する量子力学の使用として、1980年代に提案された、量子コンピュータの導入後の10年の概念でも、ちょうど抽象的な理論の段階にとどまる。1990年代半ばまで2つの量子アルゴリズム：ショールアルゴリズム＆nbsp;[3]（分解と離散対数の難しさの多数を解決するための多項式時間）とグローバーアルゴリズム＆nbsp;[4]（加速の二乗を提供するために、網羅的探索問題の非構造化データ用）提案されたので、量子コンピューティングは、抽象的な理論の段階から飛び出し、物理キャリアの研究開発に転じ、新しい段階は、現在量子計算と呼ばれています。新しい段階は現在、量子コンピュータと呼ばれている。以下の図は、1998年から2026年までの量子コンピュータの物理量子ビット開発のロードマップを示している。

量子コンピューティングは万能薬ではなく、すべてのコンピューティング問題の解決策ではありません。現在のところ、自然界で発生するプロセスのシミュレーション（化学・生物工学）、解読（サイバーセキュリティのために、ほとんどの伝統的な暗号システムを破る）、最適化（金融、サプライチェーンのために、実行可能なオプションの中から最適解を見つける）、およびその他のドメイン固有の問題に使用することができ、その計算優位性を発揮します。

ブロックチェーンが現在広く利用されているのは、基盤となる暗号技術によって提供されるセキュリティの上に構築された、異なる主張者間のコラボレーションに新たな信頼の基盤をもたらすという事実に由来します。

信頼されるアイデンティティとトランザクションの確認：非対称公開鍵と秘密鍵のペアに基づき、信頼されるアイデンティティを確立し、統一された方法でアイデンティティ情報を管理します。デジタル署名によってデジタル資産の認証を実現し、秘密鍵所有者の効果的な署名が実際に資産の所有権を持ちます。

コアコンセンサスと運用の安全性：ハッシュ関数、閾値署名、検証可能なランダム関数などの最新の暗号技術に基づいてコンセンサスメカニズムを構築し、コンセンサスメカニズムの安全性を確保する。

プライバシー保護と安全な共有：ゼロ知識証明、安全なマルチパーティ計算、完全同型性、その他の豊富な機能を持つ暗号技術に基づいてプライバシー保護スキームを構築し、ブロックチェーン上のデータの安全な共有を実現する。

制御可能な規制と準拠アプリケーション：リング署名、同型暗号方式、暗号アドレス、秘密共有などの暗号技術を統合して展開し、ブロックチェーン取引の安全な規制を確保する。

これには公開鍵暗号の使用が含まれ、大きく分けて、チェーン上のトランザクションにおける改ざんを防ぐために使用されるデジタル署名メカニズムと、ノード間の通信に使用される安全な伝送プロトコルがあります。上記の公開鍵暗号は、Shorのアルゴリズムの影響により、その安全性を実質的に保証することができない。暗号解読に特化した量子コンピュータの大規模な適用に必要な時間を考慮する一方で、ブロックチェーンに保存されているデータをどれだけの期間保存する必要があるか、既存のブロックチェーンシステムを量子レベルのセキュリティにアップグレードするのにどれだけの時間がかかるかも考慮する必要がある。後者2つの合計が前者よりも大きな時間の合計になる場合、ブロックチェーン上のデータは量子コンピューティングがもたらす深刻なセキュリティの脅威にさらされることになる。

量子コンピューティングの急速な発展がもたらした演算能力の増大という現状を考慮すると、現在、セキュリティリスクに効果的に対処できる主な技術的道筋は2つある：

ブロックチェーン上のデータは、量子コンピューティングがもたらす深刻なセキュリティ脅威にさらされる。
Post-quantum cryptography based on new mathematical puzzles without aid of physical equipment [5] technical route;
Physical principle-based quantum cryptography with aid of specialised physical equipment [6] ；技術ルート。

着地実装検証などの様々な要因を考慮し、既存の暗号セキュリティの前提との互換性の文脈で、セキュリティ保証の長期的な進化の下でブロックチェーンを確実にするために、ポスト量子暗号マイグレーションを通じて検討することができ、ブロックチェーンをセキュリティの量子レベルにアップグレードするために先に展開されます。理想的には、既存のブロックチェーンで使用されている公開鍵暗号アルゴリズムを、量子安全なポスト量子暗号アルゴリズムにアップグレードすることで、可能な限り以下の特徴を満たす必要があります：

小さな鍵と短い署名：ブロックチェーン上のすべての取引には署名情報が含まれます。ブロックチェーン上のすべての取引には署名情報が含まれ、取引を検証するための公開鍵もチェーン上に保存される。鍵と署名が大きすぎると、ブロックチェーンの保管コストと通信オーバーヘッドが大幅に増加します。
計算効率：ブロックチェーンの運用中に各時間帯で処理できるトランザクション数は、アルゴリズム、特に署名検証アルゴリズムの実行時間に大きく関係しています。アルゴリズムの計算効率が速ければ、高性能なブロックチェーンアプリケーションをよりよくサポートできます。

ポスト量子暗号の開発状況

ポスト量子暗号とは、一言で言えば、量子コンピューターによる既存の暗号アルゴリズムへの攻撃に抵抗できる第一世代の暗号アルゴリズムである。第一世代の暗号アルゴリズム：

公開鍵暗号システム指向;
新しいタイプの数学的問題に関連する。
専門的な機器のサポートを必要としません。
量子コンピューティングの条件だけでなく、古典的な条件下でも安全です。

現在、5つの主流の構築技術ルートがあります。左から順に、格子、符号化、多変量、ハッシュ、ホモロジーです。

グリッド：グリッド上の難問に基づいています。
エンコード：デコードの難易度に基づく。
多変数：有限体上の多変数二次多項式の群の難しさに基づく。
ハッシュ：ハッシュ関数の衝突耐性に基づく。
ホモロジー：超特異楕円曲線に基づく擬似ランダムワンダリング。

新世代の暗号アルゴリズムは、もちろん標準的な暗号システムの確立を伴う。ポスト量子暗号で最も注目されるのは、国立標準技術研究所（NTST）のポスト量子暗号標準化プロジェクト[7]であり、2016年の発足以来、ポスト量子暗号の標準化は基本的に終了している。この10年近くに及ぶ標準化のスケジュールを振り返ると、NISTは4つのポスト量子暗号の標準化候補アルゴリズムを次のように公式に発表しています:

2022年7月5日 [8]:

公開鍵暗号化/キーラッピング：CRYSTALS-KYBER;
デジタル署名：CRYSTALS-Dilithium、FALCON、SPHINCS+；

この中で、CRYSTALS-KYBER、CRYSTALS-Dilithium、FALCONは格子暗号アルゴリズムであるが、3つのセキュリティ基盤は異なり、KYBERはモード格子のMLWEの難問に基づいている。KYBERはモーダル格子のMLWEという難問に基づいており、Dilithiumはモーダル格子のMLWEとMSISという難問に基づいており、FALCONはNTRU格子のSISという難問に基づいている。

2023年8月24日、CRYSTALS-KYBER、CRYSTALS-Dilithium、SPHINCS+は、それぞれFIPS203、FIPS204、FIPS205のドラフト標準になりました[9]。FIPS203、FIPS204、およびFIPS205 [9]、そしてFALCON標準は2024年に発行される予定です。

NISTが選んだ標準アルゴリズムのほとんどが、格子暗号技術のルートに基づいていることは容易にわかる。2022年に4つの標準アルゴリズムが発表されると同時に、公開鍵暗号／鍵ラッピングアルゴリズムに焦点を当てたポスト量子暗号標準アルゴリズム評価の第4ラウンドを開始することも発表されました。さらに、デジタル署名アルゴリズムの新たな公募が開始されましたが、これは第4ラウンドの評価とは独立したもので、ポスト量子署名アルゴリズムのポートフォリオを充実させることを目的としており、既存の構造格子ベースのアルゴリズムとは異なるアルゴリズム構造を持ち、アルゴリズム署名のサイズが小さく、検証速度が速い新たな提案により重点を置いています。

NIST標準に加えて、国際インターネット標準化機構IETFは、ステートフルハッシュ署名アルゴリズムXMSSをRFC 8391[10]として2018年に、LMSをRFC 8554[11]として2019年にそれぞれ標準化し、NISTに受け入れられました。

Quantum Algorithms for Cracking Lattice Ciphers

2024年4月10日、Yiran Chen氏のeprint論文「QuantumAlgorithms for Lattice Problems"[12]が学界にセンセーションを巻き起こしました。この論文は、格子問題を解くための多項式時間量子アルゴリズムを与えるもので、格子問題に基づく多くの暗号方式に大きな影響を与え、例えば、現在広く使われているLWE仮定に基づく同型暗号アルゴリズムなど、多くのアルゴリズムが量子コンピュータからの攻撃に対抗できなくなる可能性がある。論文のアルゴリズムの正しさはまだわかっていない。

LWE問題の難しさは、Oded Regev氏の論文 "On lattices, learning with errors, random linear codes, and cryptography" [13] の中で厳密に実証されています。具体的には、LWE問題の難易度を格子上の離散ガウスサンプリング問題に一般化し、それをGapSVPやSIVPなどの古典的問題に容易に一般化できる（もちろん、それぞれの問題には固有のパラメータがあり、ここでは無視する）ことを示したものである。LWE問題の難易度が厳密に低下した後、その単純な構造から、（同形）暗号、署名、鍵交換などの基本的な暗号プリミティブから、IDベース暗号、属性ベース暗号などの高度な暗号プリミティブまで、LWEに基づく暗号方式が数多く登場しました。その中でも、業界で最も広く使用されているのは、完全同型暗号化と、前述のNISTが発表したポスト量子標準アルゴリズム（KYBER、Dilithiumなど）です。

概要

この論文は、公開されると学界に大きな波紋を呼び、多くの専門家の間で多くの議論が巻き起こった。しかし、論文の内容を理解するのが非常に難しいため、論文の内容を完全に理解できる学者は世界で5人以下かもしれず、論文の正しさを完全に検証するには1～2年かかるかもしれない。現在、一部のフォーラム、公共ウェブサイト、Zhihuなどのプラットフォームで、多くの人が関連する意見を表明しているが、いずれも論文のアルゴリズムが正しいかどうかの影響を分析しており、論文のアルゴリズムの正しさについて結論を出せる人はいない。その中で、有名な暗号学者であるN. P. Smart氏は、ブログ記事「Implications of the Proposed Quantum Attack on LWE」[14]を公開し、この攻撃の影響といくつかの洞察を詳しく述べており、要約すると以下のようになります：

この論文はまだ査読を受けておらず、正しいことが検証されたとしても、量子コンピュータに依存しているため、量子コンピュータがまだ利用できない限り、現在使われている暗号方式には何の影響もありません。
論文で示された結果によると、NISTが以前に示した標準化アルゴリズムKyber、Dilithiumを破ることはまだできませんが、NISTはこれらのアルゴリズムのパラメータを再評価する可能性があります。
BFV/CKKS/BGVのような一般的に使用されているRLWEホモモーフィック暗号化アルゴリズムについては、これらのアルゴリズムは本稿の攻撃能力の範囲内です。しかし、学術的にも産業的にも、同型暗号の「同型性」は「量子耐性」よりも魅力的であり、「量子耐性」を追求してRLWE同型暗号を使う人は少ないだろう。RLWEホモモーフィック暗号は、量子アルゴリズムが長い間提案されてきた離散対数問題に依存する楕円曲線ベースの暗号方式に似ていますが、それらは今でも学界や産業界で研究され、使用されています。

更新：チェン氏の論文の計算に問題があり、グリッド暗号の警告は一時的に解除されました。

[1] https://ethresear.ch/t/how-to-hard-fork-to-save-most-users-funds-in-a-quantum-emergency/18901/9
[2]。物理システムとしてのコンピュータ：チューリング機械に代表されるコンピュータの微視的量子力学的ハミルトニアンモデル[J]。
[3] Shor P W. Algorithms for quantum computation: discrete[3]量子計算のアルゴリズム：離散対数と因数分解[C]//Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994: 124-134.
[4]Grover L K. A fast quantum mechanical algorithm for database search[C]//Proceedings of the twenty-eighth annual ACM symposium on Theory of computing.1996年: 212-219.
[5] Bernstein, D.J. (2009).
[5]Bernstein、D.J.、Buchmann、J.、Dahmen、E. (eds) Post-Quantum Cryptography.
[6] Gisin N, Ribordy G, Tittel W, et al.量子暗号[J]。 Reviews of modern physics, 2002, 74(1): 145.
[7] https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardisation
[8] https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardised-and-round-4
[9] https://csrc.nist.gov/News/2023/three-draft-fips-for-post-quantum-cryptography
[10] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. Mohaisen, J.and A. Mohaisen, "XMSS: eXtended Merkle Signature Scheme", RFC 8391, DOI 10.17487/RFC8391, May 2018, <https://www.rfc-editor.org/info/rfc8391>。
[11] McGrew, D., Curcio, M., and S. Fluhrer, "Leighton-Micali Hash-Based Signatures", RFC 8554, DOI 10.17487/.RFC 8554, April 2019, <https://www.rfc-editor.org/info/rfc8554>.
[12] Chen Y. Quantum Algorithms for Lattice Problems[J].
[13] Regev O. On lattices, learning with errors, random linear codes, and cryptography[J].暗号[J]。 Journal of the ACM (JACM), 2009, 56(6): 1-40.
[14] https://nigelsmart.github.io/LWE.html