中国の研究者が主張する量子コンピュータによるRSA暗号の解読は間違いである可能性が高そうだ

masapoco
投稿日 2023年1月6日 14:08
crypto

最近、中国の24人の研究者がarXivに投稿した「Factoring integers with sublinear resources on a superconducting quantum processor(PDF)」という新しい論文によって、論争が巻き起こっている。

この論文では、量子コンピュータを使って2,048ビットの大きな半素数を因数分解するという新しいアプローチを提案しており、物理的な量子ビットが372個、ゲート深さが数千のNISQレベルのコンピュータで実現可能だと述べている。もしこれが実現すれば、現在のインターネットで非対称暗号として広く使われているRSA-2048暗号を危うくし、世界中のデジタル通信インフラを不安定にすることになる。ちなみに、よく知られているショアのアルゴリズムでは、誤り訂正を行うために約4,000個の論理的な量子ビットが必要で、これは物理的な量子ビットでは約2,000万個、誤り訂正に伴うオーバーヘッドによりゲート深さは数十億個になる。

昨年報告した論文で紹介したアプローチは、Claus Peter Schnoor博士が提案した古典的なアルゴリズムから始まり、整数の因数分解に格子縮小を用いる最短ベクトル問題(SVP)アルゴリズムを用いたアプローチに基づいている。今回の論文では、ショアのアルゴリズムをQAOA(Quantum Approximated Optimization Algorithm)と呼ばれる発見的量子最適化アルゴリズムと組み合わせて、ショアのアルゴリズムを高速化し、理論的にはもっと速く問題を解くことができるという新展開がなされているのだ。

このアプローチに対して、量子コンピュータの専門家からいくつかの反論が投稿されている。最初のものはScott Aaronson氏が自身のブログに投稿したもので、彼はQAOAが「いかなる高速化ももたらすという説得力のある議論はまだなされていない」と述べ、ただ一つの可能性のある例外を挙げている。また、この論文自体が、「QAOAの曖昧な収束のため、アルゴリズムの量子的な高速化は不明」と言及していることを指摘している。Moody’s Analyticsは、「Schnorr技法が適切にスケールすることが示されなかった」と指摘する論文を掲載している。その他にも、QAOAアルゴリズム自体がうまくスケールできない可能性があること、この手法を使ってもゲートレベルフィデリティ99.999%のNISQコンピュータが必要であることなどが明らかにされていないとのことだ。このレベルは、現在ある最高のマシンよりも2桁以上優れている。99.999%を達成するためには、まだ誤り訂正が必要かもしれない。最後に、QAOAは、ある問題に対して絶対的な最適化をもたらすことが保証されているわけではないことを指摘している。ユースケースによっては、たとえ2番目か3番目の最適解を提供したとしても、古典的なものよりも良い、あるいはより速い答えを提供できるのであれば、それはまだ有用なものだろう。しかし、因数分解ではそのようなことはない。答えは厳密でなければならず、2番手ではうまくいかない。

とはいえ、この論文が間違っていることが判明したとしても、それはこれから起こることへの警告であることは間違いない。米国政府は、実際の量子ブレークスルーに直面して、キー暗号化標準がいかに早く陳腐化するかについて、ますます懸念を強めている。昨年5月、ホワイトハウスは連邦政府機関に対し、運用において耐量子暗号化に迅速に移行するよう指示している


Source



この記事が面白かったら是非シェアをお願いします!


  • amazon echo dot
    次の記事

    Amazon、今春からEchoデバイスに「Matter-over-Thread」をサポートすると発表

    2023年1月6日 14:34
  • 前の記事

    ニューヨーク市が公立学校でのAI利用を禁止すると発表

    2023年1月6日 13:55
    student at school

スポンサーリンク


この記事を書いた人
masapoco

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です


おすすめ記事

  • 4960135107578d6a564d5bee03e5cdb6

    史上初、時間結晶を用いて量子コンピュータを制御し安定性を高める事に成功

  • fc39f96786dd592fc77c942cb8ba1285

    革新的なアルゴリズムにより、古典コンピュータが量子コンピュータを超えることが可能に

  • newroom quantum hardware.rendition.intel .web .1920.1080

    量子コンピュータの実現に向けた新たな融合材料の生成に成功

  • QuEra、世界初のフォールトトレラント量子コンピューターを2024年末までにリリースへ

  • Alice Bob LDPC Cat Qubits Picture

    新たなエラー訂正技術が量子コンピュータの小型化を実現する可能性

今読まれている記事