Post-Quantum Cryptography

Lattice-based cryptography is built on the computational hardness of problems like the Learning With Errors (LWE) and Shortest Vector Problem (SVP) in high-dimensional lattices. This is the most versatile and widely studied approach in PQC.

• NIST Standards: The selected algorithms CRYSTALS-Kyber (key encapsulation) and CRYSTALS-Dilithium (digital signatures) are lattice-based.
• Security: Security relies on the apparent difficulty of finding short, non-zero vectors in a random lattice, a problem believed to be resistant to quantum algorithms like Shor's.
• Attributes: Offers strong security proofs, relatively efficient operations, and enables advanced cryptographic features like fully homomorphic encryption (FHE).

Code-based cryptography relies on the difficulty of decoding a general linear code, known as the syndrome decoding problem. The classic example is the McEliece cryptosystem, proposed in 1978.

• Longevity: It has remained unbroken since its invention, providing confidence in its classical and post-quantum security.
• Performance: Offers very fast encryption but has large public key sizes (often hundreds of kilobytes to megabytes).
• NIST Standard: A variant, Classic McEliece, was selected by NIST for key encapsulation. Its security is based on well-studied algebraic coding theory.

Multivariate cryptography is based on the difficulty of solving systems of multivariate quadratic polynomials over finite fields. The core hard problem is the Multivariate Quadratic (MQ) problem.

• Signature Focus: This approach is primarily used for digital signatures, as encryption schemes have historically been less efficient.

• NIST Standard: CRYSTALS-Dilithium (a lattice-based scheme) was the primary selection, but the multivariate-based FALCON was also standardized for use cases requiring smaller signatures.

• Structure: Private keys are typically a trapdoor (a structured, easy-to-solve map) hidden within a seemingly random public set of equations.

Hash-based cryptography constructs digital signature schemes whose security depends solely on the cryptographic collision resistance of an underlying hash function (e.g., SHA-256, SHA-3).

• Quantum Resistance: Security is reduced to the hardness of finding hash collisions or pre-images, problems where Grover's quantum algorithm provides only a quadratic speedup, which can be mitigated by doubling the hash output size.
• Stateful vs. Stateless: XMSS and Leighton-Micali Signature (LMS) are stateful schemes standardized by NIST and IETF, requiring careful management of a one-time-use private key index. SPHINCS+ is a stateless, but larger, alternative.
• Use Case: Considered a conservative, high-assurance option for long-term signature needs where key state can be managed.

A leading family of post-quantum cryptographic algorithms whose security relies on the computational hardness of mathematical problems involving high-dimensional geometric structures called lattices. These problems, like the Learning With Errors (LWE) and Shortest Vector Problem (SVP), are believed to be resistant to attacks by both classical and quantum computers. Lattice-based schemes are favored for their strong security proofs, efficiency, and support for advanced cryptographic features like fully homomorphic encryption. The NIST-selected CRYSTALS-Kyber for key encapsulation is a lattice-based algorithm.

A class of PQC algorithms whose security is based on the difficulty of decoding random linear error-correcting codes, a problem known to be NP-hard. The most famous example is the McEliece cryptosystem, proposed in 1978. Its main advantages are high-speed operations and a long history of cryptanalysis without significant breaks. Drawbacks include large public key sizes (often hundreds of kilobytes to megabytes). NIST selected the code-based Classic McEliece as a finalist for key encapsulation, primarily for its conservative security assumptions.

Public-key cryptosystems based on the difficulty of solving systems of multivariate quadratic polynomials over finite fields. The security relies on the fact that solving such nonlinear systems is generally NP-complete. These schemes typically have very fast encryption and signature verification but can have large public keys. They are primarily used for digital signatures. NIST selected the multivariate-based CRYSTALS-Dilithium and FALCON as primary and alternate standard signature algorithms, respectively, due to their strong performance and security.

Digital signature schemes whose security depends solely on the cryptographic collision resistance of an underlying hash function (like SHA-256 or SHA-3). They are considered one of the most conservative and well-understood approaches to post-quantum signatures because hash functions are easier to analyze and are already widely trusted. The trade-off is that they are stateful, meaning the signer must carefully track which one-time keys have been used to prevent forgery. The SPHINCS+ scheme, a stateless hash-based signature, was standardized by NIST as a backup option.

A relatively newer family of PQC that uses the mathematical theory of elliptic curves and mappings between them called isogenies. Security is based on the presumed difficulty of computing an isogeny between two supersingular elliptic curves. The primary advantage is extremely small key sizes compared to other PQC approaches. The main proposed scheme, SIKE, was a NIST finalist but was later broken using a classical attack in 2022, highlighting the importance of ongoing cryptanalysis. Research in this area continues with new constructions.