注意喚起情報

CRYPTREC ER-0001-2019

現在の量子コンピュータによる暗号技術の安全性への影響

2020年(令和2年)2月17日
CRYPTREC 暗号技術評価委員会

今般、ゲート型の量子コンピュータが量子超越を実現したと主張する論文がNature誌に発表されました^[1]。この論文では、ランダム量子回路からのサンプリング問題を、古典計算機を用いた場合には1万年かかるところ、量子コンピュータを用いると200秒で完了すると主張しています。この主張は、ランダム量子回路からのサンプリング問題を、量子コンピュータが古典計算機よりも高速に解くことを示しています。これにより、現在広く使用されている公開鍵暗号であるRSA暗号及び楕円曲線暗号などの安全性が大きく低下することが一部で懸念されています。その理由としては、それらの暗号技術が安全性の根拠として利用している素因数分解問題と離散対数問題が、大規模な量子コンピュータとShorのアルゴリズムを使用することで高速に解読されることが知られているためです。

現在、CRYPTREC暗号リストの電子政府推奨暗号リストに記載されているRSA-PSS、RSASSA-PKCS1-v1_5、RSA-OAEPは素因数分解問題を、DSA、ECDSA、DH、ECDHなどは離散対数問題を安全性の根拠にしています。CRYPTRECでは、以前よりRSA合成数の素因数分解などにおける安全なパラメータサイズについて、通常の計算機だけでなく、量子コンピュータによる影響に関しても評価を行っておりますが、今までの評価結果をふまえると、CRYPTRECとしては、近い将来にCRYPTREC暗号リスト記載の暗号技術が危殆化する可能性は低いと考えています。

論文^[1]で使用されている量子コンピュータは53量子ビットであり、計算は合計1543回のゲート演算で構成されています。このとき、1回当たりの計算時間は、1マイクロ秒程度であると見積もられています。なお、ターゲットとする問題の性質上、量子誤り訂正は組み込まれていません。

その一方で、例えば、量子コンピュータを用いて2048ビットRSA合成数の素因数分解を行う場合には、量子誤りが一切ないという理想的な環境下でも、4098量子ビットが必要であり、10¹²～10¹³回のゲート演算が必要であると見積もられています^{[2, 3]}。また、量子誤りがあるという現実的な環境下では、2000万量子ビットが必要であるという見積もりもあります^[4]。

このため、実現されている量子コンピュータと素因数分解を行うのに必要とされる量子コンピュータの性能に関しては、依然として大きな乖離があります。これは離散対数問題を利用する暗号についても同様です。量子コンピュータの性能を測る上での指標（量子ビット数、量子誤りの大きさ、演算可能回数など）や、量子コンピュータの開発状況もあわせて考慮にいれると、近い将来に、2048ビットの素因数分解や256ビットの楕円曲線上の離散対数問題が解かれる可能性は低いと考えます。

しかしながら、革新的な技術の発展などにより、量子コンピュータで暗号解読を実現する可能性は否定できません。このため、CRYPTRECでは、量子コンピュータによる暗号技術に対する影響、及び量子コンピュータ実現後にも安全な暗号技術（耐量子計算機暗号）に関する監視評価活動を継続していきます。

ご意見・コメントなどの問い合わせがございましたら、下記までお願いいたします。

CRYPTREC事務局
E-mail:

1. Quantum supremacy using a programmable superconducting processor
   https://www.nature.com/articles/s41586-019-1666-5
2. National Academies of Sciences, Engineering, and Medicine. 2019. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press.
   https://doi.org/10.17226/25196
   日本語訳版:
   E. Grumbling, M. Horowitz 編, 西森 秀稔 訳, “米国科学・工学・医学アカデミーによる量子コンピュータの進歩と展望,” 共立出版, 2020.
3. NICTサイバーセキュリティシンポジウム
   https://www.pco-prime.com/2019cybersympo/
4. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
   https://arxiv.org/abs/1905.09749