Post-Quantum Cryptography

The majority of NIST-selected algorithms rely on the computational hardness of lattice problems, specifically Learning With Errors (LWE) and Ring-LWE. Security is based on finding the shortest vector in a high-dimensional lattice, a problem believed to be intractable even for Shor's algorithm.

• CRYSTALS-Kyber: A Module-LWE-based Key Encapsulation Mechanism (KEM) selected for general encryption.
• CRYSTALS-Dilithium: A Module-LWE signature scheme offering small public keys and fast verification.

These schemes construct signatures solely from the security of cryptographic hash functions, requiring no global state management between signing operations. They offer extremely conservative security assumptions but produce larger signatures.

• SPHINCS+: The only stateless hash-based scheme standardized by NIST. It uses hypertrees of Winternitz One-Time Signatures (WOTS+).
• XMSS and LMS: Stateful alternatives approved for specific use cases like firmware signing, where managing state is feasible.

Security relies on the difficulty of decoding a general random linear error-correcting code, a problem known to be NP-complete. This is one of the oldest areas of quantum-resistant research, dating back to the McEliece cryptosystem.

• Classic McEliece: A NIST finalist using binary Goppa codes. It features very large public keys (hundreds of kilobytes) but extremely small ciphertexts and fast, time-tested operations.
• Syndrome Decoding: The fundamental hard problem: finding a low-weight error vector given a parity-check matrix and a syndrome.

These schemes base their security on the difficulty of solving systems of multivariate quadratic polynomials over finite fields, a problem proven NP-hard. They typically produce very short signatures but have historically suffered from key recovery attacks.

• Oil and Vinegar: A trapdoor construction where variables are split into 'oil' (secret) and 'vinegar' (public) sets.
• Rainbow: A NIST finalist (now broken) that used a multi-layer unbalanced oil-and-vinegar structure, demonstrating the volatile cryptanalysis landscape.

To mitigate 'harvest now, decrypt later' threats, PQC is deployed alongside classical ECC in hybrid mode. This concatenates a classical signature with a PQC signature, ensuring security holds if either scheme remains unbroken.

• Composite Certificates: X.509 extensions binding both an ECDSA and a Dilithium public key to a single identity.
• TLS 1.3 Hybrid Key Exchange: Combining X25519 with Kyber-768 in a single ClientHello to protect session keys against future quantum retrospection.

While mathematically quantum-resistant, PQC implementations introduce new physical attack surfaces. Lattice-based schemes are vulnerable to power analysis and electromagnetic leakage during Gaussian sampling and number-theoretic transforms (NTT).

• Masking Countermeasures: Boolean and arithmetic masking applied to Kyber's decapsulation to prevent differential power analysis (DPA).
• Constant-Time NTT: Ensuring the number-theoretic transform executes in a data-independent time to prevent timing side-channels that leak secret key coefficients.

The mathematical foundation for the majority of NIST-standardized post-quantum algorithms. Security relies on the hardness of lattice problems like Learning With Errors (LWE) and Ring-LWE, which remain intractable even for large-scale quantum computers running Shor's algorithm.

• Underpins CRYSTALS-Kyber (KEM) and CRYSTALS-Dilithium (signatures)
• Provides the security basis for most efficient Fully Homomorphic Encryption schemes
• Operations involve noisy inner products over high-dimensional integer lattices

A defense-in-depth strategy combining post-quantum key encapsulation with homomorphic encryption to secure AI inference pipelines. PQC protects data in transit and at rest against harvest-now-decrypt-later attacks, while HE protects data in use during computation.

• CRYSTALS-Kyber establishes a quantum-secure channel for transmitting HE public keys
• Prevents an adversary from decrypting captured ciphertexts once a cryptographically relevant quantum computer emerges
• Essential for long-lifetime sensitive data processed in sovereign AI clouds

The National Institute of Standards and Technology completed its third-round selection in 2024, standardizing algorithms designed to replace RSA and ECC. The selected schemes span multiple mathematical families to hedge against future cryptanalytic breakthroughs.

• FIPS 203: ML-KEM (Kyber) for general key establishment
• FIPS 204: ML-DSA (Dilithium) for primary digital signatures
• FIPS 205: SLH-DSA (SPHINCS+) for stateless hash-based signatures as a conservative backup