2025年5月21日、Google Quantum AIの研究者クレイグ・ギドニー氏は、RSA-2048暗号の因数分解に必要な量子ビット数を従来の推定値から大幅に削減できる可能性を示した論文をarXivに発表した。
2019年の研究では、2000万のノイズを含む量子ビットで8時間の計算時間が必要とされていたが、今回の研究では、100万未満のノイズを含む量子ビットで1週間以内に因数分解が可能とされている。
この削減は、近似剰余アルゴリズム、ヨークド・サーフェスコード、といった技術的改良によるもので、Toffoliゲートの使用回数も従来比で100分の1に削減された。これにより、量子コンピュータによるRSA暗号の解読が、予想よりも早期に現実化する可能性が示唆されており、暗号技術の専門家に対して、耐量子計算機暗号（PQC）への移行を促す警鐘となっている。
from:Quantum computers may crack RSA encryption with fewer qubits than expected
【編集部解説】
今回の研究は、RSA-2048暗号の安全性に対する量子コンピュータの脅威が、予想よりも早く現実化する可能性を示しています。特に、必要な量子ビット数が大幅に削減されたことは、量子コンピュータの実用化に向けた進展を加速させる要因となるでしょう。これにより、暗号技術の専門家やセキュリティ担当者は、耐量子計算機暗号（PQC）への移行を急ぐ必要があります。
また、今回の研究で使用された技術的改良は、量子コンピュータの性能向上だけでなく、他の計算問題への応用も期待されます。特に、近似剰余算術やヨークド・サーフェスコード、マジックステートの栽培といった手法は、量子計算の効率化に寄与する可能性があります。
現在の量子コンピュータは、必要とされる数百万の量子ビットには達していませんが、技術の進展速度を考慮すると、RSA暗号の安全性に対する脅威が現実味を帯びてきています。そのため、企業や政府機関は、量子時代に備えたセキュリティ対策を早急に講じる必要があります。
【用語解説】
- RSA暗号：1977年に開発された公開鍵暗号方式で、データの暗号化と復号に使用される。大きな素因数分解の困難性に基づいている。
- 量子ビット（qubit）：量子コンピュータにおける情報の最小単位で、0と1の重ね合わせ状態を持つ。
- ノイズを含む量子ビット（noisy qubit）：エラーや外部環境の影響を受けやすい実際の量子ビットで、エラー訂正が必要となる。
- 近似剰余算術（Approximate Residue Arithmetic）：モジュラー演算を近似的に行う手法で、量子回路の深さを削減し、必要な量子ビット数を減少させる。
- ヨークド・サーフェスコード（Yoked Surface Codes）：表面コードを格子手術で結合した階層型エラー訂正コード。
- Toffoliゲート：3つの量子ビットを操作する量子論理ゲートで、量子アルゴリズムにおいて重要な役割を果たす。
- 耐量子計算機暗号（Post-Quantum Cryptography, PQC）：量子コンピュータによる攻撃に耐性を持つ暗号方式で、NISTなどが標準化を進めている。
- ショアのアルゴリズム（Shor’s Algorithm）：1994年にピーター・ショアが発表した、整数の素因数分解を効率的に行う量子アルゴリズムで、RSA暗号の安全性を脅かすとされる。
【参考リンク】
- Google Quantum AI
Googleの量子コンピューティング研究部門。量子アルゴリズムやハードウェアの開発を行っている。 - arXiv: How to factor 2048 bit RSA integers with less than a million noisy qubits
クレイグ・ギドニー氏による論文。RSA-2048の因数分解に必要な量子ビット数を大幅に削減する手法を提案している。 - NIST Post-Quantum Cryptography Project
米国国立標準技術研究所による、量子耐性を持つ暗号方式の標準化プロジェクト。
