Post-Quantum Cryptography

Table of Contents

1. Introduction
2. What Is Post-Quantum Cryptography?
3. Quantum Threat to Classical Cryptography
4. Shor’s and Grover’s Algorithms
5. Timeline of Cryptographic Vulnerability
6. Goals of Post-Quantum Cryptography
7. Differences Between PQC and Quantum Cryptography
8. Criteria for PQC Schemes
9. NIST Standardization Project
10. Classes of PQC Algorithms
11. Lattice-Based Cryptography
12. Code-Based Cryptography
13. Multivariate Polynomial Cryptography
14. Hash-Based Cryptography
15. Isogeny-Based Cryptography
16. Symmetric Key Systems and Quantum Attacks
17. Hybrid Cryptography Approaches
18. PQC Digital Signatures
19. PQC Key Encapsulation Mechanisms (KEMs)
20. Real-World Deployment Challenges
21. Performance and Resource Constraints
22. Quantum-Resistant TLS/SSL
23. PQC in IoT and Embedded Systems
24. Migration Strategies
25. Conclusion

1. Introduction

Post-Quantum Cryptography (PQC) refers to cryptographic algorithms that are secure against the threat posed by quantum computers. Unlike quantum cryptography, PQC does not rely on quantum mechanics but is designed to resist attacks by quantum algorithms.

2. What Is Post-Quantum Cryptography?

PQC is the field of designing, analyzing, and standardizing cryptographic schemes that remain secure in the presence of a large-scale quantum computer. The focus is on public-key cryptography, which is most vulnerable.

3. Quantum Threat to Classical Cryptography

Quantum algorithms such as:

• Shor’s Algorithm can break RSA, ECC, and DH
• Grover’s Algorithm speeds up brute-force attacks

This renders much of today’s cryptographic infrastructure insecure in a quantum future.

4. Shor’s and Grover’s Algorithms

• Shor’s Algorithm solves integer factorization and discrete log problems in polynomial time.
• Grover’s Algorithm provides a quadratic speedup for brute-force search:
• Reduces symmetric key strength by half (e.g., AES-256 → AES-128 equivalence)

5. Timeline of Cryptographic Vulnerability

While large-scale quantum computers are not yet available, the data harvested today may be decrypted in the future — a threat known as “store now, decrypt later.”

6. Goals of Post-Quantum Cryptography

• Quantum resistance: Secure even with quantum adversaries
• Backwards compatibility: Deployable in current infrastructure
• Efficient: Reasonable performance on modern hardware

7. Differences Between PQC and Quantum Cryptography

8. Criteria for PQC Schemes

• Security under quantum attacks
• Performance (speed, size, memory)
• Robustness and simplicity
• Proven cryptographic foundations
• Resistance to side-channel attacks

9. NIST Standardization Project

In 2016, NIST began a competition to standardize PQC schemes. In 2022, it announced Round 3 selections:

• Kyber (lattice-based) for key exchange
• Dilithium and Falcon for signatures
• SPHINCS+ (hash-based) as a fallback

10. Classes of PQC Algorithms

1. Lattice-based
2. Code-based
3. Multivariate polynomial
4. Hash-based
5. Isogeny-based

Each has different trade-offs in security, efficiency, and implementation complexity.

11. Lattice-Based Cryptography

Based on the hardness of lattice problems like:

• Shortest Vector Problem (SVP)
• Learning With Errors (LWE)

Pros:

• Efficient
• Strong security proofs

Examples:

• Kyber (KEM)
• Dilithium (Signature)

12. Code-Based Cryptography

Relies on the difficulty of decoding random linear codes.

Example: McEliece Cryptosystem
Pros:

• Long-standing resistance to quantum attacks
  Cons:
• Very large public keys

13. Multivariate Polynomial Cryptography

Uses multivariate quadratic equations over finite fields.

Example: Rainbow (broken in 2022)
Pros:

• Fast signature generation
  Cons:
• Key generation can be slow and bulky

14. Hash-Based Cryptography

Based on Merkle trees and cryptographic hash functions.

Example: SPHINCS+
Pros:

• Very conservative, minimal assumptions
  Cons:
• Large signature sizes

15. Isogeny-Based Cryptography

Based on elliptic curve isogenies.

Example: SIDH (Supersingular Isogeny Diffie-Hellman)
Pros:

• Very small keys
  Cons:
• SIDH was broken in 2022; trust in this class has diminished

16. Symmetric Key Systems and Quantum Attacks

Symmetric schemes like AES and SHA are quantum-resistant with larger key sizes:

• AES-256 is still safe
• Hash functions must be double the classical strength to resist Grover’s algorithm

17. Hybrid Cryptography Approaches

Combining classical and PQC schemes:

\[
\text{Hybrid Encryption} = \text{Classical KEM} + \text{PQC KEM}
\]

Used in TLS (e.g., Google Chrome and Cloudflare experiments)

18. PQC Digital Signatures

Crucial for:

• Software updates
• Code signing
• Identity verification

Standardized options: Dilithium, Falcon, SPHINCS+

19. PQC Key Encapsulation Mechanisms (KEMs)

Used in:

• TLS handshake
• VPN key exchanges
• Email encryption

Kyber is the leading candidate.

20. Real-World Deployment Challenges

• Larger key and signature sizes
• Compatibility with protocols like TLS, SSH, VPNs
• Speed vs memory trade-offs
• Implementation bugs and side channels

21. Performance and Resource Constraints

Some schemes (e.g., McEliece) require megabytes of memory, which is infeasible for embedded systems.

22. Quantum-Resistant TLS/SSL

• Google, Microsoft, and AWS have tested PQC-enhanced TLS
• Hybrid handshakes: Classical + PQC
• PQC integration into OpenSSL and TLS 1.3 is ongoing

23. PQC in IoT and Embedded Systems

• Resource-constrained devices (e.g., smart cards, sensors) require:
• Compact key sizes
• Low CPU usage
• Lightweight PQC schemes are being explored

24. Migration Strategies

Organizations should:

1. Inventory cryptographic dependencies
2. Use hybrid schemes during transition
3. Test and pilot PQC integrations
4. Stay updated with NIST and international standards

25. Conclusion

Post-Quantum Cryptography is essential for safeguarding digital infrastructure against future quantum threats. By using classical mathematics but quantum-resilient designs, PQC offers a practical path forward for modern cryptography. With ongoing standardization, real-world deployments, and growing industry support, PQC will soon become a foundational part of the security landscape in the quantum era.