RSA暗号が使えなくなる…!?　暗号解読を行う新しい量子アルゴリズム

・研究者たちは、より少ないリソースで暗号解読の計算を行う新しい量子アルゴリズムを開発しました。

・2,000万量子ビットの量子コンピュータでこのアルゴリズムを動かすと、2,048ビットのRSA暗号を解読するのにわずか8時間しかかかりません。

秘密のメッセージの送信に使われている既存の暗号コードを量子コンピュータが解読できるようになることは確実です。これまでの暗号化技術は、完全に信頼できるものではありませんでした。その代わり、このような暗号化技術は一方向にしか働かない複雑な数学関数に依存しているため、情報の暗号化が容易です。

このような技術の安全性は、従来のコンピュータが情報の解読に要する時間に基づいています。現代の暗号化技術は、現在のコンピュータがその暗号を解読するのに何千年もかかるため、ほとんど破られていないのです。

しかし、量子コンピュータならばこれらの暗号を簡単に解読することができますし、またこのようなコンピュータは予想されていたよりずっと現実に近いものとなっています。

最近、Googleとスウェーデン王立工科大学の研究者たちは、量子コンピュータ上で秘密のメッセージを解読できる、より効率的な技術を考え出しました。それを用いれば、量子コンピュータはより少ないリソースで暗号解読の計算を行うことができるというのです。

力の強さを増す量子コンピュータ

1994年にアメリカの数学者ピーター・ショアは大数の因数分解を行う量子アルゴリズムを開発し、従来のコンピュータ上で動作する既存のものの中で最良のアルゴリズムと比べて、因数分解の速度を指数関数的に高速化しました。彼は、十分な性能を持つ量子マシンがあれば、現代の暗号技術を簡単に破ることができると示唆しました。

ここ10年で、量子コンピュータは大きく進歩しました。2012年に科学者たちは、4量子ビットの量子コンピュータを使って「143」を因数分解することに成功しました。その2年後には、同様のマシンを使って「56153」の因数分解に成功しています。

この進歩の速さを考えると、量子コンピュータは近いうちに現在のコンピュータを凌駕するようになるでしょう。少なくとも、数年前の科学者たちはそう予想していました。

しかし、量子コンピュータで大数を因数分解することは、予想以上に難しいことがわかりました。これは、大型の量子コンピュータには大きなノイズがあるためです。この問題に対処するには誤り訂正符号を用いることが考えられますが、それには余分な量子ビットが必要となります。

このノイズ要因を考慮すると、2048ビットの数字を因数分解する、つまり2048ビットのRSA暗号を復号するためには、10億量子ビットの量子コンピュータが必要となります。しかし、現在の一般的な量子コンピュータには70個の量子ビットしか搭載されていません。

モジュラー指数関数

この新しいアルゴリズムにより、量子コンピュータはわずか2,000万量子ビットでこれらの計算を行うことができます。実際、研究者たちは、この新しいアルゴリズムで動作する量子デバイスが2,048ビットのRSA暗号を解読するのにわずか8時間しかかからないことを示しました。

“これは、2048ビットのRSA整数を因数分解するのに必要な量子ビット数についての最悪な推定値が、約2桁下がったことを意味します。” – と研究チームは述べています。

この方法では、モジュラーを用いた指数関数の一種であるモジュラー指数関数を効率的に実行することができます。ショアのアルゴリズムだと、この数学的操作の計算量が多いのです。

研究者たちは、この演算を最適化するさまざまな方法を発見し、アルゴリズムの実行に必要なリソースを劇的に削減しました。

2000万量子ビットの量子コンピュータが近い将来には実現できないとしても、セキュリティの専門家たちは、強力な量子コンピュータでも解読できないような新しい暗号を考えなければなりません。