量子コンピューターの登場によってもRSA暗号システムは破られないかもしれない

量子コンピューターの登場で、現在に普及しているRSA暗号システムを計算によって突破できる可能性があり、暗号システムの危機が叫ばれています。しかし、ペンシルバニア大学の研究チームが、新たに量子コンピューターによっても破ることのできないRSA暗号鍵を作出するアルゴリズムを開発したと発表し、RSA暗号鍵システムが量子コンピューターに対抗できる可能性が示されています。

Cryptology ePrint Archive: Report 2017/351
https://eprint.iacr.org/2017/351

Why Quantum Computers Might Not Break Cryptography
https://www.quantamagazine.org/why-quantum-computers-might-not-break-cryptography/

RSA暗号システムの基本的なアイデアは、巨大な数の素因数分解が古典的なコンピューターでは難しいことを利用しています。巨大な素数同士のかけ算は簡単でも、掛け合わした巨大な数を素因数分解するには膨大な時間がかかり現実的には不可能なので、掛け合わした数を公開鍵に、素因数分解した素数を秘密鍵にすることで、秘密鍵を持つものだけが暗号を解除できるというのが公開鍵暗号システムであり、現在の一般的な暗号システムとして、インターネットの世界の暗号化技術を支えています。

しかし、1994年に素因数分解を多項式時間で解けるアルゴリズムをMITのピーター・ショア教授が考案したことで、準指数時間で素因数分解を解くことができるアルゴリズムしかもたない古典コンピューターでは不可能な巨大な数の素因数分解であっても、量子コンピューターを使えば現実的な時間内に解けることが分かり、RSA暗号システムが突破される可能性が高まりました。量子コンピューターの実用化によって、既存の暗号システムが無力化されてしまうことから「暗号システムの危機」と言われているわけです。

量子コンピューターの前にはRSA暗号システムは歯が立たないという通説に対して、ペンシルバニア大学のナディア・ヘニンジャー准教授らの研究チームが、テラバイト級の暗号鍵を効率的に作るアルゴリズムを考案しました。このテラバイト級暗号鍵を用いたRSA暗号システムを解読するには、量子コンピューターでも2の100乗という膨大な数の演算処理が必要だとのこと。2の100乗がどのくらい大きい数かというと、地球上にいる全バクテリアの細胞数の半分だとのことで、量子コンピューターでさえ現実的な時間内には計算できないとしています。

現在RSA暗号システムで使われている暗号鍵のサイズは数千ビットなのに対して、テラバイト(数兆ビット)級の暗号鍵を作ることで暗号システムを解読できないようにするという力業による対抗策ですが、ペンシルバニア大学の研究チームが開発したアルゴリズムでも暗号鍵の作成・暗号解読に5日かかるとのことなので、おいそれとは使えない代物で実用レベルとは言い難いものだそうです。ただし、従来言われていた「量子コンピューターによってRSA暗号システムが崩壊する」という見解を大きく否定する技術である可能性はありそうです。ヘニンジャー准教授は、「実用性はさておき、従来の通説的な知見が間違いだというのが分かるのは面白いものです」と述べています。

・おまけ
RSA暗号システムの共同発明者のアディ・シャミア教授が、科学技術の進歩に貢献した功績をたたえられ日本国際賞を受賞しましたが、受賞会見で「量子コンピュータを研究している人たちより楽観的には考えていて、ここ10年や15年の間に量子コンピュータが暗号を解読するようなことはないと思っている」と述べています。

ニュース解説 - 「RSA暗号は量子コンピュータで破られない」、生みの親が日本国際賞受賞で熱弁：ITpro
http://itpro.nikkeibp.co.jp/atcl/column/14/346926/042700954/