Grover's Algorithm
Definition
Grover's algorithm is a quantum search algorithm discovered by Lov Grover in 1996 that provides quadratic speedup for unstructured search problems. For cryptography, this effectively halves the security level of symmetric algorithms and hash functions, requiring doubled key and hash sizes for equivalent security.
Technical Explanation
Grover's algorithm searches an unsorted database of N items in O(√N) time, compared to O(N) for classical algorithms. For a 256-bit key, brute-force search classically requires 2²⁵⁶ operations; Grover's algorithm requires 2¹²⁸ quantum operations—still astronomical but representing a halving of security bits.
Importantly, Grover's provides only quadratic speedup—much less dramatic than Shor's exponential advantage. Doubling key lengths from 128 to 256 bits fully compensates. AES-256 and SHA-256 remain secure against Grover's algorithm with current parameters.
SynX Relevance
SynX accounts for Grover's algorithm in all parameter selections. Kyber-768 provides 192-bit post-quantum security (accounting for Grover's). SPHINCS+ hash parameters target sufficient security margins. All symmetric operations use keys and hashes sized for quantum resistance.
Frequently Asked Questions
- Does Grover's algorithm break AES?
- No—AES-256 retains 128-bit security against Grover's, which remains computationally infeasible.
- Is Grover's algorithm as dangerous as Shor's?
- No—Grover's provides quadratic speedup (easily compensated); Shor's provides exponential speedup (catastrophic).
- Does Grover's affect signatures?
- Only hash-based signature security levels, easily addressed by parameter selection.
Parameters designed for Grover's resistance. See SynX security specifications