量子超越性への不確かな道のり：RSA覚書

不確実性。RSA Conference 2018の会場を歩き回り、量子コンピューター、そして起こり得るサイバーセキュリティ上の危険をテーマとするセッションに参加した私の思いを表すのに、これ以上ない言葉です。そういう思いを持つのは私だけではありません。最初の基調講演で行われたクリプトグラファーによる恒例のパネルディスカッションでは、サイバーセキュリティ業界に対する脅威の1つとして「量子コンピューティング能力の隆盛」が挙げられていました。しかし結局それがいつ起こるのか、具体的な予測の話はありませんでした。そこで今日は、さまざまな領域にある点をつないで、あちこちに散らばった知識の波動関数を崩壊させ、ある程度の理解に達するように努力してみましょう。

不確実性。量子力学においては一般的なことながら、普段の生活やビジネスでは私たちが排除しようとするもの。人は普通、確実でないことに対して恐怖を抱きます。業界関係者の中には、暗号化されたデータが量子コンピューティングによってすべて解読されてしまう日が来るのを恐れる人も少なくありません。そして、その恐怖には根拠がないわけではない。すべては量子超越性（量子スプレマシー）が理由です。

量子超越性とは、テクノロジーが成熟して、従来のコンピューターにはできなかったタスクを量子コンピューターができるようになるという仮説的状況を言い表す言葉です。そのようなタスクの1つ（科学にとってはさほど重要でなくとも、業界にとっては重要なもの）は積の素因数分解、コンピューティング能力的に言えば非対称のオペレーションを実行することです。このタスクでは、チェック（乗算）にはほとんど時間がかかりませんが、因数分解には膨大な時間がかかります。現在使われている暗号化スキームのほとんどは、この時間の長さを利用しています。

とはいえ、「量子超越性」という言葉の定量的定義は比較的新しく、このNature Physicsの記事（英語）に掲載されている内容がほぼ最新です。Nature Physicsの編集者は、量子超越性実現のしきい値をおよそ50量子ビットと見積もっています（英語記事）。つまり、最近発表された72量子ビットのGoogle Bristlecone（英語記事）で乗算の結果から素因数分解すると、世界一有名なスーパーコンピューターが負ける可能性があるということです。これは憂慮すべきでしょうか？

答えはYesでもあり、Noでもあります。物事の状態を確実に把握する者などいない量子の世界では、Yesであると同時にNoでもあるのです。冗談はさておき、あなたやあなたのクライアントが暗号化された情報を長期間保存するつもりなら「Yes」ですし、そうでないなら「No」です。

しかし「長期間」とはどれほどの長さなのでしょうか。その日に備えて準備をするための期間は、どれほど残されているのでしょうか。アルゴリズムによって答えは違ってきます。BT Americasのセキュリティコンサルティング担当CTO、コンスタンティノス・カラヤンニス（Konstantinos Karagiannis）氏はRSAで登壇し、鍵長が512ビットの対称アルゴリズム（DES、AES）がまず解読され、その時点で量子ビットは100を超え、512ビットのメッセージは数分のうちに因数分解されると予測しました。鍵長4,096ビットの非対称アルゴリズム（RSAなど）の場合は、同様に数分で解読するには1,000量子ビット以上必要であるとしています。

先ほど触れましたが、Bristleconeもまだそのレベルには達していません。しかしムーアの法則が量子コンピューターにも当てはまるとすれば、来年にはそのレベルに達するかもしれません。この前提で2018年3月を起点に計算すると、仮説上144量子ビットになったBristleconeが、512ビット鍵の対称暗号化を破るのは、2019年後半あたりであると予測できます。4,096ビット鍵の非対称暗号化の場合は、1,152量子ビット程度のチップが登場するまでの約6年間、つまり2025年の後半までは時間的猶予があるようです。この年数はあくまで仮説であり、新しいテクノロジーの採用などは勘案されていません（それには時間が足りません）。そして残念ながら、この予測を検証する方法はありません。最も性能の良い最新のスーパーコンピューターであっても、それほど大きな量子ビットを持つ量子コンピューターをエミュレートすることはできないからです。

ともかく、私たちには今後に備える時間がいくらかは残されています。そのときが来た後も暗号化されたデータを保存するつもりがないのであれば、心配する必要はありません。国際的な規制機関や地域当局の場合は、量子コンピューターにも破られないアルゴリズムを2025年までに考え出しておく必要があります。保存データを暗号化しないか（良い考えではありませんが）、保存データの定期メンテナンス（データを時々復号してさらに強力なアルゴリズムで暗号化するなど）を実施するか、というところでしょう。

量子コンピューターに破られない標準を当局が考え出すまで待てないならば、ハイブリッドテクノロジーを活用できるかもしれません。つまり既存の最高レベルの暗号化テクノロジー（RSAなど）で十分な長さの鍵を使用し、楕円曲線暗号（ECC）のアルゴリズムと組み合わせるという方法です。前者は従来の方法で破ることはできませんし、後者は今の最新コンピューターでは解読される可能性があるものの、量子コンピューターには耐えられると考えられています。この組み合わせでデータの安全性を保つには十分でしょうし、少なくとも迫り来る量子コンピューティング時代への備えにはなるでしょう。同時に、暗号化テクノロジーの進歩をよく観察し、新しいアルゴリズムが利用できる段階（量子コンピューターに解読されないことが証明済み）になったら、すぐに採用するのが得策です。

デジタルコンピューティングの非対称性に依存するテクノロジーは、このほかにもあります。たとえばブロックチェーンは、量子ハッキングの最大の被害者となる可能性があります。「量子コンピューターへの耐性を持つようになる」のためのロードマップを公表しているのは、今のところEthereumだけです。そういえば、ワンタイムパッド（1882年に考案された古典的手法）には、量子ハッキングの力が及ばないことをお話しし忘れていました。中規模企業と大規模企業ではすでに使用されている、量子鍵配送を活用した光ファイバーソリューションも、崩壊不確実性の時代に備えるための実行可能なオプションとなるかもしれません。それ以上のことは、不確実なままです。