ShorのアルゴリズムとGroverのアルゴリズム

量子コンピューターは、従来のアルゴリズムを単に高速に実行するだけではありません。量子重ね合わせと干渉を利用して、特定の問題を指数関数的に高速に解決します。広く導入されている暗号技術を脅かすアルゴリズムは2つあります。ShorのアルゴリズムはRSA/ECCを破り、Groverのアルゴリズムは共通鍵暗号とハッシュの安全性を低下させます。

Shorのアルゴリズム（1994年）は、量子コンピューター上で整数の素因数分解と離散対数問題を多項式時間で解きます。これにより、素因数分解に基づくRSA、mod p上の離散対数に基づくDiffie-Hellman、楕円曲線離散対数に基づくECDH/ECDSAが直接破られます。

Shorのアルゴリズムの要となるのが、量子版のDFTであり、指数関数的に高速な量子フーリエ変換（QFT）です。周期発見では、QFTによって f(x) = a^x mod N の周期を特定し、その周期からGCDを使ってNの因数を導き出します。

Nを素因数分解する手順は次のとおりです。(1) N未満のランダムなaを選び、gcd(a,N)=1であることを確認します。(2) QFTを使って f(x)=a^x mod N の周期rを求めます。(3) 高い確率で、gcd(a^{r/2}±1, N)から自明でない因数が得られます。古典的な手順はO(log N)、量子による周期発見はO((log N)^3)で、いずれも多項式時間です。

古典的な素因数分解で最も優れた手法はGNFSで、計算量は準指数時間のO(exp((64/9 log N)^{1/3} log log N)^{2/3}))です。フォールトトレラント量子コンピューター上のShorのアルゴリズムは、多項式時間のO((log N)^3)で実行できます。RSA-2048の解読には、約4000個の論理量子ビットと約10^9回のゲート演算が必要です。現在のNISQコンピューターは約1000個のノイズの多い量子ビットしか備えていないため、まだ脅威にはなっていません。

Groverのアルゴリズム（1996年）は、構造化されていない探索を二次的に高速化します。N個の項目からなる探索空間では、古典的なアルゴリズムはO(N)回のクエリを必要としますが、GroverのアルゴリズムではO(√N)回で済みます。暗号技術に適用すると、nビットの共通鍵をO(2^n)ではなくO(2^{n/2})で破れるようになります。

AES-128の古典的な安全性は2^128ですが、Groverのアルゴリズムによって2^64まで低下し、大規模な量子コンピューターに対して安全ではなくなります。AES-256は2^256から2^128に低下しますが、依然として安全です。対策は、共通鍵のサイズを2倍にすることです。SHA-256の衝突耐性は2^128から2^85（birthday+Grover）に低下します。SHA-256の原像計算量は2^256から2^128となり、問題ありません。

現在のNISQ量子コンピューター（IBM Heronは133量子ビット、Google Sycamoreは70量子ビット）は小さすぎ、ノイズも多いため、暗号技術に関連する計算には適していません。RSA-2048の解読時期は、フォールトトレラント量子コンピューターが実現した場合で2035～2050年と見積もられています。harvest-now-decrypt-later攻撃は、現在すでに脅威となっています。

攻撃者は現在、暗号化された通信を収集して保存します。量子コンピューターが利用可能になると、それらをさかのぼって復号します。そのため、長期間にわたって機密性が必要な情報（政府の機密データや医療記録）は、現在すでに危険にさらされています。このようなデータについては、PQCへの移行を今すぐ開始する必要があります。

格子問題（LWE、SIS）、符号ベースの問題（McEliece）、ハッシュベースの署名（SPHINCS+）、多変数問題には、現在知られている多項式時間の量子アルゴリズムがありません。これらは、NISTの耐量子暗号標準の基盤となっています。

NISTのPQC標準（ML-KEM、ML-DSA、SLH-DSA）は2024年に最終決定されました。組織は、現在の暗号技術の利用状況を棚卸しし、長期間保存されるデータを特定し、鍵交換のPQC導入を優先する必要があります。鍵交換はharvest-now-decrypt-later攻撃の影響を受けるため、最も緊急性が高く、署名にはより多くの時間があります。

GroverのアルゴリズムはAES-128にどのような影響を与えますか？

Shorのアルゴリズム（多項式時間）はRSA、DH、ECCを破ります。Groverのアルゴリズム（二次的な高速化）は、共通鍵の強度を半分にします。対策は、NISTのPQC標準（格子ベース）へ移行することです。次はCRYSTALS-Kyber KEMです。