新量子アルゴリズムで2000万量子ビットが2048ビットRSAを8時間で解読

量子コンピュータが秘密通信に使われる既存暗号を破れることは確実視されています。これらの暗号技術は完全に信頼できるものではなく、片方向にしか機能しない複雑な数学関数に依存しており、暗号化は容易ですが復号には古典コンピュータで数千年かかります。

しかし量子コンピュータなら容易に破れ、その実現は予想より近いかもしれません。Googleとスウェーデン王立工科大学（KTH）の研究者たちが、量子コンピュータがより少ないリソースで解読計算を行える効率的な手法を開発しました。

量子コンピュータの進化と課題

1994年、ピーター・ショアが古典コンピュータ上の最良アルゴリズムより指数関数的に高速に大きな数を因数分解する量子アルゴリズムを開発。十分強力な量子マシンなら現代暗号を容易に破れると示唆しました。

過去10年で量子コンピューティングは大きく進歩。2012年に4量子ビットで「143」を、2014年に「56153」を因数分解。しかし大規模量子コンピュータの著しいノイズにより、大きな数の因数分解は予想より困難であることが判明。誤り訂正コードで対処可能ですが、それ自体が追加量子ビットを必要とします。

ノイズを考慮すると、2048ビット数の因数分解（2048ビットRSA復号）には10億量子ビットが必要とされていましたが、現在の汎用量子コンピュータはわずか70量子ビットです。

新アルゴリズムにより、わずか2000万量子ビットでこれらの計算が可能になりました。このアルゴリズムを実行する量子デバイスなら、2048ビットRSA暗号をわずか8時間で解読できます。

この手法は、ショアのアルゴリズムで計算コストが高い「モジュラ指数演算（合同式上の指数演算）」を効率的に実行します。研究者たちはこの演算を最適化する様々な方法を見つけ、アルゴリズム実行に必要なリソースを劇的に削減しました。

Reference: arXiv:1905.09749 | MIT Technology Review

2000万量子ビットの量子コンピュータは近い将来実現困難ですが、セキュリティ専門家は強力な量子コンピュータでも破れない新たな暗号形式を検討すべきです。

産業技術