Post-Quantum Cryptography

Schemes that base security on the hardness of problems over high-dimensional lattices, such as the Learning With Errors (LWE) and Ring-LWE problems. These involve solving noisy linear equations, a task believed to be intractable even for quantum computers.

• Core Problem: Finding the shortest vector in a high-dimensional lattice (SVP) or solving bounded distance decoding (BDD).
• Key Algorithms: CRYSTALS-Kyber (KEM), CRYSTALS-Dilithium (signatures), Falcon.
• Relevance to ML: Forms the mathematical foundation for virtually all modern Fully Homomorphic Encryption (FHE) schemes, including CKKS and BFV.
• Advantage: Small key sizes and fast operations compared to other post-quantum families.

Schemes relying on the difficulty of decoding a general linear code. The public key is a scrambled version of a structured code, and an attacker must distinguish it from a random code to break the system.

• Core Problem: Syndrome decoding of a random linear error-correcting code.
• Key Algorithm: Classic McEliece, which has withstood cryptanalysis since 1978.
• Advantage: Longest-standing security track record among post-quantum candidates.
• Disadvantage: Very large public keys (hundreds of kilobytes to over a megabyte), making them impractical for bandwidth-constrained applications.

Schemes based on the difficulty of solving systems of multivariate quadratic polynomial equations over finite fields, a problem proven to be NP-hard.

• Core Problem: Solving a random system of multivariate quadratic equations (MQ problem).
• Key Mechanism: Constructs a trapdoor by hiding a structured central map that is easy to invert behind two random affine transformations.
• Signature Schemes: Rainbow (now broken) and GeMSS were prominent candidates; UOV (Unbalanced Oil and Vinegar) remains a conservative choice.
• Advantage: Extremely fast signature verification, suitable for resource-constrained devices.

Stateless and stateful signature schemes whose security relies solely on the collision resistance and preimage resistance of a cryptographic hash function, making no additional mathematical hardness assumptions.

• Core Mechanism: Uses Merkle trees to combine many one-time signature (OTS) key pairs into a single, longer-lived public key.
• Key Algorithms: SPHINCS+ (stateless), LMS, and XMSS (stateful).
• Advantage: Minimal security assumptions; if the underlying hash function (e.g., SHA-256) is secure, the signature scheme is secure.
• Disadvantage: Stateful schemes require careful management of a state counter to prevent catastrophic key reuse.

Schemes based on finding explicit maps (isogenies) between elliptic curves over finite fields. The security relies on the difficulty of computing an isogeny between two given supersingular elliptic curves.

• Core Problem: Path-finding in the supersingular isogeny graph.
• Key Mechanism: SIKE (Supersingular Isogeny Key Encapsulation) was the leading candidate, using a random walk through the isogeny graph as a Diffie-Hellman-like key exchange.
• Status: SIKE was broken in 2022 by a devastating mathematical attack on a single classical computer, demonstrating the immaturity of the field.
• Advantage: Historically offered the smallest key sizes of any post-quantum KEM.