Post-Quantum Cryptography

In 2022, SIKE - a post-quantum candidate with the most compact keys - was broken by a classical algorithm in 1 hour on a laptop. PQC requires careful vetting.

• **NIST FIPS 203/204/205 (August 2024)**: the first official post-quantum standards - the PQC era has officially begun.
• **Google Chrome 2023**: hybrid X25519+Kyber for TLS connections - billions of connections already using PQC.
• **Apple iMessage PQ3 (2024)**: Kyber for daily key rotation - the strongest PQC deployment in a consumer application.
• **Signal 2024**: PQXDH protocol with Kyber for X3DH - post-quantum protection for 40M+ users.

Kyber: Lattice-Based Encryption

CRYSTALS-Kyber (now ML-KEM, FIPS 203) won the NIST 2022 competition for Key Encapsulation Mechanisms. It is based on the Module Learning With Errors (M-LWE) problem: given pairs (A, b = As + e) where s is a secret and e is small noise, recover s. This problem is believed to be hard for both classical and quantum computers. Kyber-768 provides ~AES-192 security; Kyber-1024 provides ~AES-256.

Kyber performance is comparable to RSA at the implementation level: Kyber-768 keygen takes 0.04 ms, encapsulation 0.05 ms, decapsulation 0.06 ms on a modern CPU. RSA-2048 keygen takes ~1 ms. Key sizes: Kyber-768 public key is 1184 bytes (vs RSA-2048 at 256 bytes), ciphertext is 1088 bytes. Google Chrome included Kyber in 2023 for TLS connections. Apple iMessage deployed it in 2024 (PQ3 protocol) for daily key rotation.

Dilithium: Lattice-Based Signatures

CRYSTALS-Dilithium (ML-DSA, FIPS 204) is a digital signature scheme based on Module Learning With Errors. The construction uses a Fiat-Shamir with aborts approach: the prover shows knowledge of s without revealing it. Security is based on M-LWE and M-SIS (Module Short Integer Solution). Dilithium3 (~AES-192): signature 3293 bytes, public key 1952 bytes. By comparison: ECDSA P-256 signature is 64 bytes, key is 32 bytes.

FALCON (FIPS 206) is an alternative lattice signature with smaller output (~666 bytes at AES-128 security), based on NTRU lattices, but is significantly harder to implement without side-channel leakage. Dilithium is the more conservative choice for most applications. Dilithium3 performance: keygen 0.08 ms, sign 0.1 ms, verify 0.08 ms - roughly 10x faster than RSA-2048 key generation.

SPHINCS+: Hash-Based Signatures

SPHINCS+ (SLH-DSA, FIPS 205) is the only NIST finalist not based on lattices. Its security depends entirely on the collision resistance of hash functions (SHA-256 or SHAKE). A Merkle tree combined with one-time signatures (WOTS+) and few-time signatures (FORS) forms a hierarchical scheme. Advantage: minimal security assumptions. Disadvantage: large signatures (8-50 kB).

Hash-based signatures are historically the first post-quantum signatures: Lamport OTS (1979), Merkle Signature Scheme (1989). SPHINCS+ is a modern stateless scheme without the usage limits of stateful schemes like XMSS. Applications: long-term signatures, Certificate Transparency logs, and firmware signing where signing speed is not critical. Dilithium is preferred for interactive protocols; SPHINCS+ suits batch offline signing.

Code-Based and Other PQC Approaches

Code-based cryptography is based on the hardness of decoding random linear codes (the syndrome decoding problem, which is NP-hard). McEliece (1978) is the oldest post-quantum scheme, unbroken for 45 years. Classic McEliece was included in NIST Round 4 as an alternative. Drawback: enormous public keys (Classic McEliece-8192128: public key ~1 MB). It is suitable for specialized applications with high bandwidth.

Isogeny-based cryptography (SIDH/SIKE) was another approach with the most compact keys among PQC candidates. SIKE was broken in 2022 by a classical attack (not a quantum one) by Wouter Castryck and Thomas Decru - 1 hour on a laptop. This serves as a reminder that PQC schemes can be broken by classical cryptanalysis. That is precisely why NIST ran an 8-year competition with intensive analysis. Lattice schemes have undergone the most thorough vetting.

A New Era of Cryptography

• **ML-KEM (Kyber)**: lattice-based KEM on LWE, FIPS 203. Performance comparable to RSA with larger key sizes.
• **ML-DSA (Dilithium)**: lattice-based signatures, FIPS 204. 10x faster keygen than RSA-2048; signature size 3.3 kB.
• **SLH-DSA (SPHINCS+)**: hash-based signatures, FIPS 205. Minimal security assumptions; signature size 8-50 kB.
• **SIKE broken 2022**: reminder that PQC schemes require extensive cryptanalysis - always choose NIST finalists.

Related Topics

Post-quantum cryptography is the direct response to the quantum threat and the replacement for classical asymmetric schemes.

• The Quantum Threat — Shor's algorithm is the primary motivation for developing ML-KEM and ML-DSA.
• Secret Sharing — Threshold schemes and ZKP constructions are being adapted for the post-quantum world.
• ZK-SNARKs — Lattice-based zero-knowledge proofs are an active research area within post-quantum cryptography.

Вопросы для размышления

• If Kyber has keys 5x larger than RSA-2048 at comparable performance, which practical systems will suffer most from the PQC migration?
• Classic McEliece has been unbroken for 45 years but has ~1 MB public keys. In which scenarios would these tradeoffs be acceptable?
• SPHINCS+ relies only on hash security. If SHA-256 were broken tomorrow, how would that affect the PQC migration plan?

Связанные уроки

• la-01-vectors-intro