よろずQCのZen問答:現在の暗号は直ぐに量子コンピュータの台頭で危うくなるのか？

—————————————————————————————————————

追加

これを最初出した時見つけられなかったデータを入手できたので、追加した。湊氏の見解の部分でtwitter情報を追加。

—————————————————————————————————————-

今QCが熱い。QCが最初に注目され始めた時によく言われたのが、QCが実用化されれば、多くの計算が指数関数的に速くなると。良いことばかりではなくて悪いこともある。QCが発展すれば、公開鍵暗号方式に使用されているalgorithmを逆に解くことで暗号が破られると言うものだ。理論的には正しい。問題は何時になったら、QCが十分発展して現在の公開鍵暗号方式が破られるのだろうか。

ここでは、Blueqatの湊氏のビデオとMIT Techonology Reviewの記事を元にして考察してみる。

初めに

絶対破られない暗号はまだ開発されていない。これからも、無理だろうと思うが。第二次世界大戦中に日本軍が鹿児島弁を使ったとか、米軍がアメリカインディアンのナバホ族の言葉で通信したとかいう話を聞くが。これとて完全な暗号通信にはならない。

現在使用されているRSA型の暗号（2048-bit RSA encryption）は、大きな２つの整数を掛け合わせる計算は簡単だけど、その結果を元の２つの整数に戻すための計算が莫大な時間が掛かると言う事実に基づいている。理論的には時間が無限にあれば、解読は可能である。しかし、解読に例えば100年掛かったら、解読できた頃にはもうその人はいないだろう。逆に言えば、その計算を短時間で行えば、暗号は破られる。では、計算速度を指数関数的に加速することのできるalgorithmを開発すればよい。

1994年にPeter Shorがこの計算を短時間で行うことが可能なalgorithmを開発して、現在でもShor’s algorithmとして広く知られている。Algorithmの詳細はこのblogの範囲を超えるので、ここでは述べない。残念ながら、今のNISQ上でShorのalgorithmを稼働させることはできない。そのために、今の暗号は解読される可能性は限りなくゼロに近い。安心して、銀行預金の残高チェックやAmazonで買い物をしよう。

既存の暗号に脅威を与えるQC

時が経つに連れて、RSA暗号システムがどれだけ危機に晒されているかを図解したグラフをWorld Economic Forumの記事から見つけたが、ここでは転載できないので、筆者が表示されているデータを元にグラフを再構築して見た。44人の専門家にある時点でRSA暗号が破られている確率を答えてもらった結果である。縦軸には専門家の数で横軸は時間を取ってある。それぞれの年後の部分を見てみよう。左から、RSA暗号が破られる確率は1%未満、5%未満、30%未満、50%程度、70%強、95%強、と最後に99%強と回答した専門家の数を示している。

以下実際の人数ではなく、%で議論する。5年後は61%がその可能性は1%未満であると回答したが、時間がたつに連れて高い確率で解読されるという意見が増加していく。15年後は30%弱の確率で解読されるというのが一番多いが、この時はまだ一番高い確率は95%強だという。それ以降は99%強という意見が出てくるのに注目。20年後になると70%強と回答した専門家が64%であるが、この時初めて、11%の専門家が99%強の確率でRSA暗号が破られるとしている。それ以降は言わずもがなだろう。これは私見ではあるが、QC実用化の予想スケージュールと大体合ってるようだ。

MIT Technology Reviewの記事によれば、2015年の段階でRSA型暗号を解読するには、NISQ上で数十億のqubitが必要だと結論付けている。2021年の現在でも最高のqubit数は70程度だ。ところが、GoogleのCraig Gidneyと KTH Royal Institute of TechnologyのMartin Ekeråが2021年4月に発表した新たな方式はShor’s algorithmのアル部分を変更することで、必要なqubitの数を数十億から2千万のオーダーまで落とすことができる。つまり、彼等の新しいalgorithmを利用すれば、2,000万個のqubitを搭載しているNISQがあれば、RSAの暗号は８時間で解読できる。

数十億から2,000万個に削減したのがすごいと思うのか、実質的な事態は殆ど変わらないと思うのは人によって異なるであろう。筆者はこれ１つだけ取り出して評価するのではなく、今後に期待する。今後も同様の発見や改善が見られるであろう。しかも、それぞれの進展が着実に起こりつつお互いに影響し更に改善が続くだろう。そしてある時、例えば15年後、RSA暗号が事実上意味をなさなくなり、現在社会がdigital の世界を享受できている元になる大きなインフラが崩壊してしまうかもしれない。つまりQCがShorのalgorithmを問題なく実行できるようになった時、社会そのものが崩壊してしまう。これは、QCの発展という面では、素晴らしい進歩だが、社会的には大問題だ。だから、QCの発展が社会にとっても良いことであるように、新たな暗号の仕組みが必要になってくる。

新たなAlgorithmの開発

完全なQCが完成して、RSA型暗号が役に立たなくなった時に備えての新しい暗号の動きをまとめる。

上で述べた状況では、座して死を待つのみだ。この予測がある中、QCを持ってしても破られないRSA暗号システムに取って変わる暗号方式を定めなければならない。しかも、その方式は標準でなければならない。そのため米国の標準を定めるNISTが量子コンピュータでも解読されない新しい世代の暗号方式を公募して、広く応募(69件）があった。それは、Post-Quantum Cryptography PQCと呼ばれ、2016年にスタートした。QCが実用化された後の新しい方式は大きく分けて６種類ある。既に２度応審査が行われており、審査の度に、応募者が選択されて応募者が減少していく。現在は３度目で、審査に残っているの応募方式は15で、そのリストはここにある。PQCの内容はこの記事によくまとまっている。更に、NISTはこの件に関する最後のWhite Paperを発表している。この記事とWhite Paperに関しては、このblogの範囲を超えるのでこれ以上はここでは述べない。

なんだか、いつもの事だけど全ては米国主導かと嘆く貴方に朗報。このところ良いニュースのない我らが東芝がやってくれました。東芝の“絶対に破られない”「量子暗号通信」開発責任者を直撃　市場の4分の1を取ってリーディングカンパニーへの記事から。。。。

企業や政府機関に対するサイバー攻撃が相次ぎ、解読できない暗号が注目される中で、「理論上、盗聴が不可能な量子暗号通信」といわれる将来的に有望な暗号技術の開発に成功したのだ。東芝は2035年度に全世界で約200億ドル（約2.1兆円）と見込まれる量子鍵配送サービス市場の約4分の1（2030年度で約30億ドル［約3150億円］）を獲得し、量子暗号通信業界のリーディングカンパニーを目指すとしている

“絶対に破られない”「量子暗号通信」開発責任者を直撃　市場の4分の1を取ってリーディングカンパニーへより

東芝の件はこれ以上触れないので、後は各自記事を参照のこと。

湊氏の見解

湊氏は早くからQCビジネスを展開しており、ビジネスだけなく技術面に関しても詳しいので、氏の見解は聞くに値する。上のビデオの内容をまとめると。

1. 米国のDarpaはQCでRSA暗号を解読できるようになるのは2040年頃と推定。これに対して、湊氏は2050-260年頃と予想。湊氏はDarpaの情報をTwitterから入手した。そのtwitterからの写真を欄外に示す。（注：この情報は新たに追加。）
2. Shor’s algorithmはQCのkiller applicationである。それを支えるalgorithmはQAE (Quantum Phase Estimation)で、暗号だけでなく、量子化学計算や機械学習などにも使われる。
3. 2015-2020年の間では、QPEがNISQ上で稼働できないので、量子化学計算などには、代わりに近似的に結果を提供するVQEが開発された。しかし、2019年のGoogleによる量子超越性のデモにより、VQEへの期待がFTQC上のQPEに移動してきた。
4. 完全なFTQCではないが、IonQやHoneywellのion trap型のQCの発展などに伴いQPEが更に改善される見込み。それに伴い量子化学計算はVQEからQPEに向かう。更に、QPEの進歩で今まであまり取り上げられてこなかった暗号や機械学習も進展する。
5. 暗号は一番難しいので、暗号の問題が解決するということは、他の問題も全て解けていることになり、俄に信じがたい。これが、湊氏のDarpaの2040年説に対しての反応である。筆者の受け取りは、2040年というと今から約20年後で、上のグラフだと、70%強の確率でRSA暗号が危うくなっていると考える専門家が一番多い。Darpaがこのデータから2040年と言ってるのかは不明だが、見事に一致している。暗号が破られるかもしれないということに対しては早い目に手を打つべきだということからかもしれない。更に、新たな暗号方式が設定されても、実用化には数年かかるだろうし、実際の現場の暗号を新たなものに置き換えるには数年からひょっとすると10年単位の時間が必要かもしれない。そういう意味では、10-20年くらいは誤差の範囲かもしれない。
6. しかし、物事が進むときは加速度に進むこともある。ただし、全ては、ハードとソフトのどちらも進展しないと簡単ではない。

考察

QCの実用化と言う話、ちょっと前までは少なくとも10年、人によっては20-30年先という話だった。しかし、最近思ったより早く実現するという記事が目立っている。例えば、上で引いたMITの記事、先日のGoldman Sachsの記事などだ。ちょっと角度は違うが、こういう記事もある。「PsiQuantum and GLOBALFOUNDRIES Claim Quantum Computing Breakthrough」。PsiQuantum社とGlobal Foundries社が共同で100万個以上のqubitを搭載するQCを発表した。光子ベースでかつシリコンベースだ。この発表だけでは、このQCがどの程度FTQCなのか判断に苦しむが、突然このような新しい動きが現れるので驚かされる。湊氏は最近のビデオで、2020-2021年はNISQからFTQCに移る過渡期なため、多くの方式が生まれては廃れていくかも知れず、どれがどのタイミングで生き残るかわからないため、多くを学ぶ必要があり、この時期にQCの分野に参入した人や会社は大変だと述べている。ああああ。。。大変な時にblogを書き始めてしまった。いや、そうではない。実に美味しいのだと告白しておこう。

最後に、QCの分野では、Breakthruは起こるだろうし、着実な進歩も起こるだろう。そして我々は過度に期待せず、そうかと言って過度に失望せず前進することが大切だと思う。どのような技術も、過剰な期待、過度の失望の繰り返しだろうと思う。直ぐに実現すると思ったことが意外に時間が掛かったり、長くかかると思ったことが比較的短時間で到達できたことは技術革新の中では、幾つもあった。しかし、それぞれが非常に異なっているため、あまり過去は参考にならない。しかし、冬の時代は避けられない。AIが冬の時代でも、deep learningを殆どの人々が諦めた時、カナダマフィアが諦めなかったために、今のdeep learningがある。QCに関しても、同様に絶対諦めない研究者がいると信じたい。