Grover のアルゴリズム.

N 件の非構造データから目印付きの要素をおよそ sqrt(N) 回の問い合わせで見つける量子探索アルゴリズムであり、対称暗号やハッシュ関数に対して二次の高速化を与える。 サイバーセキュリティの 暗号 カテゴリに属します。

N 件の非構造データから目印付きの要素をおよそ sqrt(N) 回の問い合わせで見つける量子探索アルゴリズムであり、対称暗号やハッシュ関数に対して二次の高速化を与える。

Grover のアルゴリズムは Lov Grover が 1996 年に発表した量子探索アルゴリズムで、ブラックボックス関数の目印付き入力を O(sqrt(N)) 回の問い合わせで見つけ出します。古典では O(N) が必要であり、暗号への影響として対称プリミティブやハッシュ関数の実効安全性が半分になります。具体的には AES-128 は約 64 ビット相当、SHA-256 の原像耐性は約 128 ビット相当まで低下します。一般的な対策は鍵長やダイジェスト長を倍にすることで、AES-256 や SHA-384・SHA-512 を採用すれば Grover 型攻撃を考慮しても十分な余裕が残ります。Shor のアルゴリズムと異なり、Grover 単独で公開鍵暗号が破られるわけではありません。

Grover のアルゴリズム に対する防御は通常、上記の定義で述べたとおり、技術的統制と運用上の実践を組み合わせます。

一般的な別名: Grover 探索。