Loading your learn pack…
Read the summary, then start training!
Quantum computers threaten public-key systems based on factoring and discrete logarithms because Shor’s algorithm can solve these problems efficiently.
Post-quantum cryptography (PQC) develops cryptographic algorithms designed to remain secure against sufficiently powerful quantum computers. Quantum computers running Shor’s algorithm could efficiently solve the integer-factorization, discrete-logarithm, and elliptic-curve discrete-logarithm problems underlying RSA, Diffie–Hellman, and elliptic-curve cryptography. Although current quantum computers cannot yet break these systems, organizations must begin migration because sensitive data captured today could be decrypted later. Mosca’s theorem provides a framework for assessing the urgency of this transition. PQC research focuses mainly on lattice-based, code-based, hash-based, multivariate, and isogeny-based cryptography. Lattice-based schemes such as ML-KEM (Kyber) and ML-DSA (Dilithium) were among NIST’s first finalized standards in 2024, while hash-based signatures provide conservative security based on well-studied hash functions. In contrast, symmetric cryptography and hash functions are comparatively resistant to quantum attacks: Grover’s algorithm provides only a quadratic speedup, which can generally be mitigated by increasing key sizes, such as using 256-bit symmetric keys for approximately 128-bit post-quantum security. PQC algorithms often involve trade-offs, including larger keys, ciphertexts, signatures, or computational costs, and migration planning should also preserve properties such as forward secrecy.
Quantum computers threaten public-key systems based on factoring and discrete logarithms because Shor’s algorithm can solve these problems efficiently.
The harvest-now, decrypt-later threat motivates early migration to PQC, even before cryptographically relevant quantum computers exist.
Major PQC approaches include lattice-based, code-based, hash-based, multivariate, and isogeny-based cryptography.
NIST finalized ML-KEM, ML-DSA, and SLH-DSA as early post-quantum standards in 2024; code-based HQC was planned for standardization in 2025.
Symmetric cryptography generally requires larger keys rather than entirely new algorithms to resist quantum attacks, because Grover’s algorithm offers a quadratic speedup.
PQC schemes must balance security evidence, key and signature sizes, performance, implementation complexity, and support for forward secrecy.
Cryptography intended to remain secure against attacks by both classical and sufficiently powerful quantum computers.
A quantum algorithm that can efficiently solve integer factorization and discrete-logarithm problems.
A quantum search algorithm that approximately halves the effective security level of symmetric keys by providing a quadratic search speedup.
An attack strategy in which encrypted data is collected today with the expectation that future quantum computers will decrypt it.
A PQC approach whose security is associated with difficult problems involving geometric structures called lattices.
A PQC approach based on the difficulty of decoding general error-correcting codes, exemplified by the McEliece system.
Digital signature schemes whose security relies primarily on the security of cryptographic hash functions.
A property ensuring that compromise of a long-term private key does not expose previously established session keys.
NIST’s standardized lattice-based key-encapsulation mechanism, commonly associated with Kyber.
NIST’s standardized lattice-based digital signature algorithm, commonly associated with Dilithium.
“Can you explain what "Quantum computers threaten public-key systems based on factoring and discrete logarithms because Shor’s algorithm can solve these problems efficiently." means in simple terms?”