グローバーのアルゴリズムは、1996年にロブ・グローバーによって発見された量子探索アルゴリズムです。ショアのアルゴリズムが公開鍵暗号を完全に破壊するのに対し、グローバーのアルゴリズムは対称暗号とハッシュ関数に対して二次的な高速化（鍵長を実効的に半分にする）を提供します。
【図解】グローバーのアルゴリズムの影響
AES-128
256→128→64ビット安全性
→ 解読可能（危険）
→ 解読可能（危険）
AES-256
256→128ビット安全性
→ 依然安全
→ 依然安全
SHA-256
256→128ビット耐衝突性
→ 依然安全
→ 依然安全
SHA-128
128→64ビット耐衝突性
→ 解読可能（危険）
→ 解読可能（危険）
二次的高速化の意味
グローバーのアルゴリズムは、未ソートのデータベースから目的の項目を見つける際に、古典的なO(N)の探索をO(√N)に高速化します。暗号学においては、これは鍵の総当たり攻撃にかかる時間が平方根になることを意味します。
つまり、256ビットの鍵は実効的に128ビットの安全性に、128ビットの鍵は64ビットの安全性に低下します。64ビットの安全性は現代のコンピュータで破れるレベルです。
ショアのアルゴリズムとの比較
- ショアのアルゴリズム：公開鍵暗号を完全に破壊（指数関数的高速化）
- グローバーのアルゴリズム：対称暗号の安全性を半減（二次的高速化）
グローバーのアルゴリズムはショアほど壊滅的ではありません。鍵長を2倍にすれば完全に無力化できるためです。これが、AES-256がポスト量子時代にも安全とされる理由です。
BMICの対策
BMICはAES-256-PQC（量子強化鍵導出関数付きAES-256）を使用しており、グローバーのアルゴリズムによる攻撃に対しても128ビットの安全性を維持します。これは現実的に解読不可能なレベルです。