100万量子ビットでRSAを因数分解、実現可能性を示唆
量子コンピューターの進展により、従来は極めて困難とされていた暗号解読の計算量が大幅に削減される可能性がある。グーグル・クオンタム・AI（Google Quantum AI）の研究者クレイグ・ギドニー（Craig Gidney）氏が5月23日に発表した最新の論文で示された。
論文「How to factor 2048 bit RSA integers with less than a million noisy qubits（100万個未満のノイズのある量子ビットを用いて2048ビットのRSA整数を因数分解する方法）」によれば、広く使用されているRSA暗号を破るために必要な量子ビット数が、従来の2000万から100万未満へと大幅に削減可能だと推定されている。ただし、処理にかかる時間は、Toffoliゲートと呼ばれる操作が増えることで増加し、全体の実行時間は従来の8時間から約1週間に延長されると見積もられている。
具体的な技術としては、フランスの研究者シュヴィニャール（Chevignard）氏らが2024年に提案した「近似剰余算術」を採用している。この手法では、一定の誤差を許容することで計算資源を節約し、モジュラー演算の効率化を図ることで、計算に必要な量子ビット数を大幅に削減している。
また、演算中にしばらく使用しないビットの保存には、「ヨークド・サーフェスコード」技術を導入している。これにより、論理量子ビットを壊すことなく小さく維持でき、全体のビット数を圧縮できるとしている。
さらに論文では、量子演算に不可欠な特殊な状態である「マジックステート」の生成方法も見直されている。必要最小限のスペースで自給自足的に作る様式に切り替えることで、処理能力を維持しつつ、スペースを大幅に縮小できるとしている。
RSAは、データを暗号化および復号化するための公開鍵暗号化アルゴリズムだ。
ビットコインではRSAを使用せず、楕円曲線暗号（ECC）とSHA-256（ハッシュ）といった暗号技術が使われている。
しかし、ECCも「ショア（Shor）のアルゴリズム」によって破られる可能性がある。
なお、「ショアのアルゴリズム」とは、量子コンピューターによって素因数分解や離散対数問題を高速に解くことができるアルゴリズムであり、ピーター・ショア（Peter Shor）氏が1994年に開発した。
ECCでは、同じ安全性を得るために短い鍵長で済むのが特徴であり、256ビットのECC鍵は3072ビットのRSA鍵と同程度の安全性を持っている。つまり、今回の論文で取り上げられた2048ビットのRSA鍵よりも、ECCははるかに高い安全性を持つ。
しかし、量子コンピューターによる攻撃能力は予想以上のスピードで進化しており、今回のような最新の研究は、こうした攻撃が現実問題として迫っていることを示唆している。
暗号資産（仮想通貨）業界でも量子コンピューターによる暗号解読リスクに対する関心は高まっている。
量子コンピューティング研究企業プロジェクト・イレブン（Project Eleven）は4月、ビットコインの暗号を破った者に1BTCを贈呈する「Q-Day Prize」を発表した。
この賞では、量子コンピューター上で「ショアのアルゴリズム」を用いてECCを破ることを条件とし、最初に成功した個人またはチームに1BTCを贈る。
プロジェクト・イレブンは声明にて、「この賞の目的はシンプルながら緊急性が高い。量子コンピューティングがビットコインの中核的な暗号技術に対して、どれだけ実質的な脅威となり得るかを定量的に評価することにある」と述べている。
参考：論文
画像：iStock/style-photography