量子コンピュータの「グローバーのアルゴリズム」と「ショアのアルゴリズム」について

1. グローバーのアルゴリズム

何ができるか？

グローバーのアルゴリズムは、「無作為探索」や「データベース検索」に適したアルゴリズムです。

• NNN 個のデータの中から特定の値を見つける問題を、従来の手法では O(N)O(N)O(N) の試行回数が必要ですが、グローバーのアルゴリズムではこれを O(N)O(\sqrt{N})O(N​) に短縮できます。

• 特に「ハッシュ値の逆算」や「共通鍵の探索」に対して有効です。

どんな脅威になるか？

• ハッシュ関数の安全性の低下:

  • ハッシュ関数は、一方向性が安全性の基盤です。しかし、グローバーのアルゴリズムにより逆算が効率化され、ハッシュ関数の探索空間（ビット長）が半減します。

  • 例えば、SHA-256（256ビット）であれば、量子コンピュータは 21282^{128}2128 回の試行で元の値を逆算できる可能性があります。

• 共通鍵暗号の弱体化:

  • 共通鍵暗号では、鍵空間が十分に大きければ安全とされていますが、グローバーのアルゴリズムは探索空間を半減させます。

  • 128ビットの鍵は量子コンピュータに対しては安全ではなくなり、256ビットが推奨されます。

---

2. ショアのアルゴリズム

何ができるか？

ショアのアルゴリズムは、「整数の素因数分解」と「離散対数問題」を効率的に解くためのアルゴリズムです。

• 素因数分解はRSA暗号、離散対数問題は楕円曲線暗号（ECC）やDSAの基盤です。

• 従来の計算では指数時間（非常に長い時間）が必要な問題を、ショアのアルゴリズムでは多項式時間で解くことができます。

どんな脅威になるか？

• 公開鍵暗号（RSA、ECC）の崩壊:

  • RSA暗号は、大きな整数を素因数分解する困難性に依存していますが、ショアのアルゴリズムによりこの安全性が破られます。

  • ECC（楕円曲線暗号）も、離散対数問題がショアのアルゴリズムで効率的に解けるため、安全性を失います。

• デジタル署名の無効化:

  • 多くのデジタル署名（例: ビットコイン、TLS証明書）は、公開鍵暗号に依存しています。これらの署名を偽造可能になるため、電子取引やデータの改ざん防止機能が脅かされます。