2048ビットRSA暗号は量子コンピューターでいつ破られるか？

量子コンピューターによって、メッセージを安全に送信するのに使われる特定の暗号が破られるのではないかと多くの人が心配している。問題となっているのは「落とし戸」関数と呼ばれる、一方向への計算が簡単で、逆方向への計算が難しい関数を使った暗号化コードである。落とし戸関数を使うことで、データを簡単に暗号化ができる一方で、特殊な鍵を使わない限り、暗号を解読するのは非常に難しくなる。

このような暗号化システムは絶対に解読不可能というわけではない。暗号のセキュリティの裏付けとなるのは、古典的コンピューターで解読を試みた場合に膨大な時間がかかることである。現代の暗号化方法は、解読が事実上不可能になるほどの時間を費やさなければ解読できないように設計されているのだ。

しかし量子コンピューターにより、このアイデアは覆されてしまう。量子コンピューターは古典的コンピューターと比べてはるかに強力なため、こうした暗号をたやすく解読できるとされているのだ。

ここで重要な問題が持ち上がる。それは、量子コンピューターの性能がその域に達するのはいつになるのかということだ。その時が来れば、先述のような暗号化方式で守られているデータはどれも安全ではなくなってしまう。

そのためコンピューター科学者は、それほどの性能を持つ量子コンピューターがどれほどのリソースを必要とするかを計算し、開発までにかかる時間を割り出そうと試みてきた。そして出てくる答えは常に、「実現は数十年先」というものだった。

しかし今となっては考えを改めるべきだろう。その根拠となるのはサンタバーバラのグーグルに務めるクレイグ・ギドニーと、スウェーデンのストックホルムにあるスウェーデン王立工科大学のマーティン・エケラの研究だ。彼らは量子コンピューターで暗号を解読するための効率的な方法を発見し、必要なリソースを何桁という単位で削減することに成功した。

結果として、量子コンピューターはかつて誰も予想しなかったほど実現へと近づいている。この研究結果は、政府や軍、セキュリティ企業、銀行、そしてこの他にもデータを25年以上安全に保管する必要のある人にとって胃の痛くなるような話となるだろう。

まずは背景を説明しておこう。1994年に米国の数学者ピーター・ショアが、古典的アルゴリズムよりも優れた量子アルゴリズムを発見した。ショアの発見した、大きな数字を素因数分解するアルゴリズムは、落とし戸関数を使った暗号を破る上で非常に重要な要 …