Quantum Computing and Cryptography
This domain tests the impact of quantum algorithms on cryptography and the post-quantum replacements now being standardized. You need to know which primitives Shor's algorithm breaks, how much Grover's algorithm weakens symmetric keys, and which PQC families address which problem.
Quantum basics and Shor
A qubit can exist in superposition of 0 and 1; entanglement correlates qubits; measurement collapses the state. Shor's algorithm solves integer factorization and discrete logarithms in polynomial time on a sufficiently large fault-tolerant quantum computer. That breaks RSA, finite-field Diffie-Hellman, DSA, ECC/ECDH/ECDSA and ElGamal. It does not break symmetric ciphers or hashes in the same way.
Grover and symmetric keys
Grover's algorithm gives a quadratic speed-up for unstructured search. It reduces an n-bit brute-force search from 2^n to about 2^(n/2), so AES-128 provides roughly 64-bit quantum security and AES-256 provides roughly 128-bit. A common migration rule is to double symmetric key sizes and hash output lengths for the quantum era.
Post-quantum cryptography
NIST standardized ML-KEM (FIPS 203, based on Kyber, lattice-based key encapsulation), ML-DSA (FIPS 204, based on Dilithium, lattice signatures) and SLH-DSA (FIPS 205, based on SPHINCS+, hash-based signatures). Other families include code-based (McEliece), multivariate and isogeny-based schemes. PQC runs on classical computers and is distinct from quantum key distribution (QKD), which uses quantum channels to detect eavesdropping but still needs authentication.
Worked example
AES-128 has a 128-bit key, so classical exhaustive search costs about 2^128. Grover searches in about √(2^128)=2^64 steps. That is still large but far below a 128-bit security target. To retain about 128 bits of quantum resistance, choose AES-256, whose Grover cost is about 2^128. This is why “double the key size” is the standard symmetric mitigation, while RSA needs replacement rather than a bigger key.
Traps
- Saying quantum computers break AES; Grover only halves the effective bit strength.
- Assuming a large cryptographically relevant quantum computer exists today; it does not.
- Confusing QKD with post-quantum cryptography.
- Believing hashes are unaffected; Grover affects preimage search.
- Forgetting “harvest now, decrypt later,” which drives migration before the machine exists.