Post-Quantum Cryptography¶

Overview¶

Post-Quantum Cryptography (PQC), also known as quantum-resistant cryptography, refers to cryptographic algorithms that can resist attacks from quantum computers. As quantum computing technology advances, traditional public-key cryptographic systems based on integer factorization (RSA) and discrete logarithms (ECC, DH) will face serious threats.

Post-quantum cryptography aims to develop new cryptographic algorithms that remain secure even in the presence of quantum computers, providing assurance for future digital security.

Quantum Threats¶

Shor's Algorithm (1994): - Can factor large integers in polynomial time - Can solve discrete logarithm problems in polynomial time - Threatened targets: RSA, DSA, ECDSA, Diffie-Hellman, ECDH - Estimated to require approximately 2,000-4,000 logical qubits to break RSA-2048

Grover's Algorithm (1996): - Reduces search problem complexity from O(2^n) to O(2^(n/2)) - Threatened targets: Symmetric encryption algorithms (AES, ChaCha20) - Countermeasure: Double the key length (e.g., upgrade from AES-128 to AES-256)

Timeline Predictions: - Google: Plans to achieve 1 million physical qubits by 2030 - Most experts: Predict quantum computers may threaten existing cryptographic systems between 2030-2040 - "Harvest now, decrypt later": Attackers may collect encrypted data now and wait for quantum computers to mature before decrypting

Main Approaches¶

1. Lattice-Based Cryptography¶

The most promising approach, based on hard problems on lattices (such as LWE, NTRU).

Advantages: - Security based on worst-case hardness assumptions - Supports construction of Fully Homomorphic Encryption (FHE) - Relatively small keys and ciphertexts - High computational efficiency

Representative Algorithms: - CRYSTALS-Kyber (Key Encapsulation) - CRYSTALS-Dilithium (Digital Signatures) - FALCON (Compact Signatures)

2. Hash-Based Signatures¶

One-time and multi-time signature schemes based on hash functions.

Advantages: - Minimal security assumptions (depends only on hash functions) - Mature and well-understood

Disadvantages: - Larger signatures - Stateful (requires tracking the number of signatures)

Representative Algorithms: - SPHINCS+ (Stateless) - XMSS, LMS (Stateful)

3. Code-Based Cryptography¶

Based on the difficulty of error-correcting codes (such as McEliece).

Advantages: - Long history (proposed in 1978) - Strong quantum resistance

Disadvantages: - Very large public keys (hundreds of KB to MB level)

4. Multivariate Cryptography¶

Based on the difficulty of solving systems of multivariate polynomial equations.

Advantages: - Fast signature generation and verification - Relatively small signatures

Disadvantages: - Large keys - Complex security analysis

5. Isogeny-Based Cryptography¶

Based on the difficulty of computing isogenies between elliptic curves.

Advantages: - Very small keys

Disadvantages: - Slower computation - Recent security issues discovered (SIKE was broken)

NIST Standardization Process¶

Timeline: - 2016: NIST launched the post-quantum cryptographic standardization project - 2022: Third-round evaluation completed - 2024: First batch of standards published

Selected Standards (2024):

Key Encapsulation Mechanism (KEM): - CRYSTALS-Kyber (now renamed ML-KEM)

Digital Signatures: - CRYSTALS-Dilithium (now renamed ML-DSA) - FALCON (FN-DSA) - SPHINCS+ (SLH-DSA)

Fourth-Round Candidates: - Continued evaluation of additional alternative schemes

China's Post-Quantum Cryptography Competition¶

Launched in 2018: Post-quantum cryptographic algorithm competition organized by the Chinese Association for Cryptologic Research.

Results (14 winning algorithms): - 11 lattice-based algorithms: LAC, Aigis-enc, AKCN-E8, CNKE, Panda, NTTRU-KE, OKCN/T, AKCN-E5, Aigis-sig, Dilithium, Aigis-sig-II - 3 code-based algorithms: Classic McEliece, NTS-KEM, BIKE

Lattice dominance: Consistent with international trends, lattice-based cryptography dominated (11/14).

Migration Strategy¶

Hybrid Schemes: - Use classical algorithms and post-quantum algorithms simultaneously - Example: Use both ECDH and Kyber in TLS 1.3 - As long as at least one scheme is secure, the system is safe

Gradual Upgrade: - Prioritize protection of long-term data (such as government secrets, medical records) - Gradually replace existing infrastructure - Test compatibility and performance

Cryptographic Agility: - Design systems to support flexible algorithm replacement - Avoid hardcoding specific algorithms

Performance Comparison¶

Scheme Type	Key Size	Signature/Ciphertext Size	Speed
RSA-2048	Medium	Small	Medium
ECC-256	Small	Small	Fast
Kyber-768	Small-Medium	Medium	Fast
Dilithium-3	Medium	Large	Fast
SPHINCS+	Small	Very Large	Slow

Overall Assessment: Lattice-based schemes achieve a good balance between performance and security and are the most practical choice.

Blockchain Impact¶

Threat Assessment: - All ECDSA-based blockchains (Bitcoin, Ethereum, etc.) are vulnerable to quantum attacks - Addresses with exposed public keys (used addresses) are at higher risk - Addresses without exposed public keys (unused addresses) have an additional hash protection layer

Countermeasures: - Developing post-quantum signature schemes (such as Lamport, SPHINCS+) - Considering migration to quantum-resistant algorithms - Some projects have already begun exploration (such as QRL, IOTA)

Challenges: - Post-quantum signatures are generally larger, increasing blockchain storage and bandwidth requirements - Hard fork upgrades are needed

Standards Adoption¶

TLS 1.3: Major browsers and servers have begun supporting hybrid PQC key exchange.

Signal: The messaging encryption protocol PQXDH integrates Kyber.

VPN: Some VPN providers offer PQC options.

Government Requirements: The U.S., EU, and others have begun requiring critical infrastructure to adopt PQC.