暗号化
2022年の末、中国の科学者グループは論文を発表し、古典コンピューティングと量子コンピューティングを巧みに組み合わせることで、近い将来インターネットプロトコルの処理の基盤である鍵長2048ビットのRSA暗号アルゴリズムを破ることができるようになると主張しました。この脅威は、どれほど現実味があるものなのでしょうか？
量子の基礎
量子コンピューターは、非常に大きい整数を超高速で因数分解し、それによりRSA暗号を含む多数の非対称暗号アルゴリズムの鍵を解読することが理論上可能であるということは、実は昔から知られていました。量子コンピューターとは何か、どう機能するか、なぜ開発が困難なのかを詳しく説明した当社のブログ記事もありますのでご参照ください。これまで専門家らは、RSAを解読可能な規模の量子コンピューターを開発するまでには、おそらく数十年はかかると予測していました。通常、RSA鍵として使用される2048ビット長の整数を因数分解するには、ショア（Shor）のアルゴリズムを数百万Qビット（量子ビット）の量子コンピューターで実行する必要があります。つまり、これは近い将来にどうこうなるという問題ではありません。数十年かけた研究の成果として実現している現時点で最高性能の量子コンピューターでも300～400 ビットに過ぎないからです。
とはいえ、未知の問題に関する議論は盛んに行われており、セキュリティの専門家は、既にポスト量子暗号の採用を提唱しています。これは、量子コンピューターによるハッキングに耐性のあるアルゴリズムです。スムーズな移行には10年以上かかるとみられているので、2048ビットのRSA鍵が早ければ2023年にも破られる可能性があるというニュースは、まさに青天の霹靂でした。
中国からのニュース
中国の研究者たちは、10 Qビットの量子コンピューターで48ビット鍵の因数分解に成功しました。そして、わずか372 Qビットの量子コンピューターを使って、2048ビット鍵に対応するようにアルゴリズムの規模を拡大できると計算しました。その規模のコンピューターは、既にたとえばIBMなどに存在します。いずれインターネット全体の暗号システムを置き換える必要があるというのは、まあ未来のことで、これまでは実際それほど真剣に考えられていませんでしたが、突如としてそんなのんきな話ではなくなりました。ブレイクスルーをもたらしたのは、シュノア（Schnorr）のアルゴリズム（前述のショアのアルゴリズムと混同しないでください）と、量子近似最適化アルゴリズム（QAOA）のステップの組み合わせでした。
提示されたハイブリッド因数分解アルゴリズムのスキーム
シュノアのアルゴリズムは、古典的なコンピュテーションを使用した、より効率的と推定される整数の因数分解に使用されます。中国のグループは、処理の中でも最も計算が多数必要なステージに量子最適化を適用することを提唱しています。
未解決の問題
シュノアのアルゴリズムは、数学者のコミュニティではいくらか懐疑的な見方がされました。論文の記述にある「これはRSA暗号システムを破るだろう」という著者の主張は、精査にさらされ、研究者たちを納得させることはできませんでした。たとえば、有名な暗号研究者のブルース・シュナイアー（Bruce Schneier）氏は、それは「比較的小さい法、つまり中国のグループがテストしたのと同じ程度の桁であればうまくいくが、サイズが大きくなると失敗する」と言っています。また、このアルゴリズムが実際に大規模化できることを誰も証明できませんでした。
量子最適化をアルゴリズムの「最も負荷が高い」部分に適用することは、いい考えのように思えますが、量子コンピューティングの専門家は、QAOAの最適化がこのコンピューティングの問題解決に有効であるかについては懐疑的です。ここで量子コンピューターを使用するのは可能ですが、時間短縮にはつながりそうにありません。当の論文の著者たち自身も、論文の最後の結論において、この疑わしい部分について慎重に言及しています。
QAOAの収束が不確定であるため、量子によるアルゴリズムの高速化が実現するかは明確ではないことを指摘しておかなければならない。
…
さらに、量子による高速化については未知であり、RSAを量子的に解読するにはまだ長い道のりがある。
このため、どうやらこのハイブリッドアルゴリズムを古典的システムと量子システムを組み合わせたシステムに実装したとしても、一般のコンピューターでRSA鍵を推測するのと同じぐらい時間がかかるようです。
さらにありがたいことに、Qビットの数に加えて、量子コンピューターには、干渉およびエラーのレベルやゲート数など、他の重要なパラメーターがあります。必要なパラメーターの組み合わせから判断すると、2023～2024年に実現が最も見込まれるコンピューターであっても、必要な規模で中国のアルゴリズムを実行するにはおそらくふさわしくありません。
現実的な結論
暗号の大変革が到来するのはこれまで想定されていた時期に落ち着きましたが、この論文を巡る騒ぎで、セキュリティに関わる2つの課題がクローズアップされました。まず、多数提唱されている「ポスト量子標準」の中から耐量子アルゴリズムを選択する場合は、前述のシュノアのアルゴリズムのような新しい代数的手法を綿密に研究しておく必要があるという点です。次に、ポスト量子暗号に移行するためのプロジェクトの優先順位を上げることが絶対的に必要であるという点です。緊急性はないと思っていたのに、気づいた時には手遅れだったということがあるのですから。
ヒント