量子コンピュータと暗号解読はテーマとしては欠かすことのできないものです。今、量子コンピュータも新しい時代に突入しており、これまであまり活発ではなかった暗号解読の議論がこれから大幅に再燃する気配があります。それはなぜでしょうか。
量子コンピュータの段階的な発展
現在量子コンピュータのソフトウェアは段階的な発展を遂げています。それらは連続的というよりもスクラップ＆ビルドを繰り返しながら量子コンピュータの活用に向けて開発が進んでいます。
2015年ごろから量子コンピュータは盛り上がりを見せていましたが、そのころはGoogleとIBMの開発競争が過熱し、超伝導量子ビットが盛んに開発され、NISQとよばれるエラーのある小規模量子コンピュータという扱いでした。
その前は、量子コンピュータのハードウェアがなかったので、理想的な量子コンピュータを想定した量子位相推定と呼ばれる固有値計算を行うアルゴリズムが主流でしたが、NISQでは回路が長い量子位相推定は動かないということで、回路の短いアルゴリズムが開発されました。それがVQEです。VQEは回路が短いかわりに、計算式をぶつ切りにして普通のコンピュータとのハイブリッドでの計算をする必要がありました。
量子コンピュータで盛んに言われる暗号解読は理想的な量子コンピュータで固有値計算をする量子位相推定アルゴリズムを利用したshorのアルゴリズムを使う必要があります。しかし、原理的にVQEでは、shorのアルゴリズムは動きませんので、2015-2020年までは実質的に暗号解読は量子コンピュータの上では動かないということになっていました。
FTQC時代の到来
しかし、2019年から2020年ごろを境にNISQでは量子コンピュータの速度を生かすことができないという風潮になり、再度きちんとした量子コンピュータを作る必要があるということで、FTQCと呼ばれる誤り訂正付きの量子コンピュータの開発へと各社方針を変えています。
そうなるとアルゴリズムも変わってきます。それまで量子化学計算ではVQEが中心に利用されていましたが、最近ではFTQC向けの量子位相推定が再度注目されています。
そうなってくると量子位相推定の開発が進むこととなり、再度shorのアルゴリズムの開発が進み、暗号解読に向けて開発が進むことになります。
shorのアルゴリズム
暗号解読を行うアルゴリズムはshorのアルゴリズムといい、暗号の周期性を利用し、モジュロ演算と呼ばれる演算を行いますが、その周期性を位相と呼ばれる角度から求めることができます。詳しくはこちらをみてみてください。
https://speakerdeck.com/gyudon/shorfalsearugorizumu
対策は？
対策は二つです。現在のコンピュータで量子コンピュータの苦手な暗号である耐量子コンピュータ暗号の実装と、将来的に量子の力を利用した量子暗号の実装です。これらによって現在の暗号よりも強力なものを使って量子コンピュータの脅威を避けます。
いつ頃来るの？
時期は2040年ごろとも言われていますが、アメリカのDARPAプロジェクトの想定では2040年に2048ビットのRSA暗号が解かれると予想されています。時期に関してはハードウェアの開発状況によって予想が変わります。
ビットコインは？
ビットコインやブロックチェーンは暗号に立脚した技術なので、暗号が破られてしまうと面倒なことになります。既存の暗号をアップデートしたりという対策が必要になりますので、早めの対応が期待されます。
以上です。