Post-Quantum
A sufficiently powerful quantum computer (CRQC) creates a bifurcated threat landscape for modern cryptography: it fundamentally breaks current public-key (asymmetric) systems while only weakening symmetric systems.
Asymmetric Cryptography: Total Compromise (Shor’s Algorithm)
Shor’s Algorithm allows quantum computers to solve integer factorization and Discrete Logarithm Problem in polynomial time. This renders current standard public-key infrastructure insecure.
- Vulnerable Schemes: RSA (relies on factoring), ElGamal, Diffie-Hellman, and ECDSA (rely on discrete log).
- Result: An adversary can derive the private key from the public key, enabling the decryption of past and future messages and the forging of signatures.
- Mitigation: Transition to NIST Post-Quantum Cryptography (PQC) standards (e.g., lattice-based or hash-based cryptography) which rely on mathematical problems distinct from factoring/discrete logs.
Secure Channel using Symmetric Key Cryptography: Quadratic Weakening (Grover’s Algorithm)
Symmetric schemes and hash functions are generally resistant to Shor’s algorithm but are affected by Grover’s Algorithm, which provides a quadratic speed-up for unstructured search (brute-forcing).
- Impact: Grover’s algorithm effectively halves the bit-security of a key.
- Examples:
- AES-128: Reduced to 264 operations (potentially breakable).
- AES-256: Reduced to 2128 operations (remains secure).
- SHA-2: Generally remains secure if output lengths are sufficiently large.
- Mitigation: Doubling the key size (e.g., moving from AES-128 to AES-256) is generally sufficient to counteract Grover’s speed-up.
Relevant Note(s):