超高性能の量子コンピューターがもたらす新たな脅威からデータや通信を保護するため、「ポスト量子暗号」の開発が盛んになっている。なぜ量子コンピューターが従来の暗号に対する脅威となるのか、将来の量子コンピューターによる攻撃に耐えられるポスト量子暗号とはどのようなものかを解説する。
オンラインショップでの商品購入やメールの送受信、銀行やクレジッドカードのアカウント確認の際に、Webブラウザーに毎回現れる小さな南京錠のマークを気に留める人はほとんどいない。
しかし、このマークはそのオンラインサービスが、インターネット上で送信するリクエストや受信するレスポンスを暗号化するWebプロトコルであるHTTPSを使用していることを示している。HTTPSや他の形式の暗号は、パスワードや電子署名、健康記録をはじめとして、あらゆる種類の電子通信を保護している。
量子コンピューターにより、これらの暗号による防御が破られる可能性がある。
今日ではまだ能力が不足しているが、量子コンピューターの進化は早い。あと10年もすれば、あるいはもっと早く、量子コンピューターは一般的な暗号方式に対する脅威となるかもしれない。
研究者やセキュリティ会社が、将来ハッカーが仕掛けてくるであろう量子コンピューターによる攻撃に持ち耐えられる暗号化の新しい方法を競って開発しているのはこのためだ。
1. デジタル暗号はどのように機能するのか
暗号の主な種類は2つある。
共通鍵暗号方式(対称暗号とも呼ばれる)では、送信者と受信者が「共通鍵」と呼ばれる同一のデジタル鍵を用いて、データを暗号化し、復号する。
これに対し、公開鍵暗号方式(非対称暗号とも呼ばれる)では、送信者は公開されている鍵を使用してメッセージを暗号化する。暗号化されたデータを解読するためには、受信側が持つ秘密鍵が必要となる。
この2つの方法が一緒に使われることもある。たとえばHTTPSの場合、Webブラウザーは、公開鍵の暗号を使用してWebサイトの正当性を確認し、共通鍵を用いて通信を暗号化する。
暗号化における目標は、ハッカーが大規模な計算リソースを使っても、暗号化に使用されている鍵を推測できないようにすることだ。このため、RSAや楕円極性暗号などとして知られる一般的な暗号方式では、いわゆる落とし戸関数(一方向関数とも呼ばれる)を使用している。
落とし戸関数とは、鍵を作るための計算は比較的容易であるが、計算結果から元の情報を逆算するのは非常に困難となる関数である。
ハッカーは、鍵として可能性のある全ての組み合わせを試せば、暗号を解読できるかもしれない。
しかし防御側は、十進数で617桁となる2048ビットのRSA鍵など、非常に長い鍵の組み合わせを使用することで、暗号を解読されないようにしている。従来のコンピューターで秘密鍵を得るために可能性のあるすべての組み合わせを試すには、何百万年とは言わないまでも、何千年もかかってしまうだろう。
2. なぜ量子コンピューターは暗号に対する脅威となるのか
量子コンピューターが実用化されれば、ハッカーはこれまでよりもずっと速く暗号化アルゴリズムの落とし戸関数を逆算できるようになる可能性があるからだ。
1か0のどちらかの値を取るビットを処理の単位として使用する従来のコンピューターとは異なり、量子コンピューターはキュービット(量子ビット)を使う。
キュービットは、1と0の数多くの取り得る組み合わせを同時に表せる。この状態は「重ね合わせ」として知られている。また、「量子もつれ」と呼ばれる状態により、キュービットは離れた位置にある他のキュービットと互いに影響を及ぼし合うこともできる。
この2つの現象を利用することで、数個のキュービットを追加するだけで、処理能力は爆発的に高くなる。300キュービットの量子コンピューターは、観測可能な宇宙上に存在する原子の数よりも多くの値を処理できるかもしれない。
量子コンピューターの性能が従来の限界を打開できるのであれば、やがては、可能性のある全ての暗号鍵の組み合わせを、比較的短い時間で試すのに使われる可能性がある。
ハッカーはまた、特定のタスクの実行を最適化する量子アルゴリズムを利用する可能性がある。
その1つは、AT&Tのベル研究所のロブ・グローバーが1996年に発表した、量子コンピューターが可能性のある組み合わせを調べるのをずっと高速化するアルゴリズムだ。
もう1つは、当時はベル研究所に所属し、現在はマサチューセッツ工科大学(MIT)の教授であるピーター・ショアが1994年に発表したもので、量子コンピューターが整数の素因数を見つけるのを格段に速くするアルゴリズムである。
ショアのアルゴリズムは、非常に大きな素数の掛け合わせの逆算が難しいことを防御の数学的拠り所の1つとするRSAなどの公開鍵暗号システムに対し、リスクを生じさせている。
全米アカデミーズが昨年発表した量子コンピューティングに関する報告書は、ショアのアルゴリズムを使った強力な量子コンピューターであれば、1024ビットのRSA鍵を1日足らずで解読できると予測している。
3. 量子コンピューターは間もなく暗号による防御を破ってしまうのか
現在の暗号がすぐに解読されてしまう可能性は極めて低いだろう。全米アカデミーズの研究によると、量子コンピューターが本当の脅威となるには、今日最も性能の高い量子コンピューターよりもずっと高度な処理能力が必要となるという。
それでも、セキュリティ研究者が「Y2Q」と呼ぶ、量子暗号解読が大きな問題となる年は、驚くほど早くやって来るかもしれない。
2015年に研究者たちは、量子コンピューターが2048ビットのRSA鍵をたやすく解読するには10億のキュービットが必要になると結論づけた。より最近の研究では、2000万キュービットのコンピューターはこの仕事をたった8時間でやってのける可能性が示されている。
これらのキュービット数は依然として、現在最も高性能である128キュービットの量子コンピューターの能力をはるかに上回っている(キュービットカウンターはこちら)。しかし、量子コンピューターの進化を予測するのは難しい。
「量子対応」の暗号による防御策が整わない限り、オンラインでの金融取引や通信は言うまでもなく、自律型自動車から軍のハードウェアに至るまで、あらゆるものが量子コンピューターを操るハッカーの標的となる可能性がある。
何十年もデータを保存することを計画している企業や政府は全て、量子テクノロジーがもたらすリスクについて考慮しておくべきだろう。データを保護するために企業や政府が使っている暗号は、今後解読され、情報が漏洩してしまうかもしれないからだ。
より強固な防御策で大量の過去のデータを再び暗号化するには何年もかかってしまう可能性があるため、対策はできるだけ早く実施すべきだ。そして、このことがポスト量子暗号を強力に後押ししている。
4. ポスト量子暗号とは何か
ポスト量子暗号とは、従来のコンピューターを使って暗号化や復号ができるが、将来の量子コンピューターによる攻撃に耐えられる、新しい種類の暗号化の方法である。
防御策の1つとして、デジタルの鍵のサイズを大きくして、強力な計算能力を使って調べる必要がある組み合わせの数を著しく増やすというものがある。
たとえば、鍵のサイズを128ビットから256ビットへと2倍にするだけで、グローバーのアルゴリズムを用いた量子コンピューターが調べなくてはならない可能性のある組み合わせの数は元の場合の2乗となる。
別の方法として、ショアのアルゴリズムなどを用いた非常に性能の高い量子コンピューターでも解読に苦労するような、より複雑な落とし戸関数を作ることがある。研究者は格子暗号や超特異写像鍵交換といった風変わりなものを含め、幅広く研究に取り組んでいる。
最終的な狙いは、広く活用できる1つまたは数個の方法に的を絞ることだ。
米国立標準技術研究所は2016年に、政府が使用するポスト量子暗号の規格を開発するためのプロセスを開始した。すでに、当初候補となっていた69個の方法のうち26個まで絞り込んでいる。しかし、規格の草案が登場し始めるのは2022年ごろになりそうだと発表されている。
暗号テクノロジーは多くの様々なシステムに深く関わっているため、プレッシャーは大きい。それらを分析し、新しい方法を実装するにはかなりの時間がかかる可能性がある。昨年の全米アカデミーズの研究では、広く利用されていた暗号化の方法が欠陥があると示された後、完全に使われなくなるのに10年以上かかったと記されている。
量子コンピューターの進化の速度を考えると、この新しいセキュリティの脅威に取り組むための時間はそう多くはないのかもしれない。
原文はこちら(英語)。
(執筆:マーティン ジャイルズ/米国版 サンフランシスコ支局長)
This article is provided by MIT TECHNOLOGY REVIEW Japan. Copyright © 2019, MIT TECHNOLOGY REVIEW Japan. All rights reserved.
この記事は、株式会社KADOKAWAが、米Technology Review社との許諾契約に基づき、再許諾しました。一部の見出し、写真等は株式会社ニューズピックス等の著作物である場合があります。