Tutorial 8.13: Quantum Computing and Post-Quantum Security

We then explore the security implications in detail: which cryptographic primitives are vulnerable and which are not. We discuss the "harvest now, decrypt later" threat and the impact on long‑term data confidentiality. We also address the implications for digital signatures, key exchange, and authentication.

The core of the tutorial is dedicated to post‑quantum cryptography. We survey the leading families of quantum‑resistant algorithms, including lattice‑based, code‑based, hash‑based, and multivariate‑based cryptography, and we discuss the NIST standardization process that has selected several algorithms for standardization. We provide guidance on migration strategies, including hybrid cryptography (mixing classical and post‑quantum algorithms) and crypto‑agility, and we address the challenges of transitioning large, complex systems.

Finally, we discuss organizational readiness: how to conduct a crypto inventory, assess risk, develop a transition plan, and build the necessary skills and partnerships. We emphasize that the transition to post‑quantum cryptography is not a single event but a multi‑year journey that requires proactive planning, investment, and coordination.

By the end of this tutorial, you will have a deep understanding of the quantum threat and a practical roadmap for preparing your organization for the post‑quantum era. This tutorial is essential for security architects, CISOs, and anyone responsible for long‑term data protection.

1. Quantum Computing Fundamentals

1.1 Quantum Concepts

Quantum Computing harnesses the principles of quantum mechanics to perform computations. Two key principles are:

• Superposition: A quantum system can exist in multiple states simultaneously. In classical Computing a bit is either 0 or 1. In quantum Computing a qubit can be in a superposition of both 0 and 1 at the same time, enabling parallel computation.
• Entanglement: Two or more qubits can become entangled, meaning the state of one qubit is correlated with the state of another, regardless of the distance between them. This enables powerful correlations that are used in quantum algorithms.
• Interference: Quantum amplitudes can interfere constructively or destructively, allowing quantum algorithms to amplify correct answers and cancel out incorrect ones.

A quantum computer operates by applying a sequence of quantum gates (unitary operations) to qubits, performing a computation, and then measuring the qubits to obtain the result. The measurement collapses the superposition to a classical state (0 or 1).

1.2 Qubits

A qubit (quantum bit) is the basic unit of quantum information. Unlike a classical bit, which is either 0 or 1, a qubit can be in a state represented as:

where α and β are complex numbers representing the probability amplitudes of the qubit being in state |0⟩ or |1⟩, and |α|² + |β|² = 1.

Qubits can be implemented using various physical systems: superconducting circuits (used by IBM, Google), trapped ions (IonQ), photons, or neutral atoms. Each implementation has its own challenges in terms of coherence time, error rates, and scalability.

Current quantum computers have between tens and a few hundred qubits, but they are noisy intermediate‑scale quantum (NISQ) devices, meaning they are error‑prone and cannot yet run long, complex algorithms without error correction. The race is on to build fault‑tolerant quantum computers with error correction, which will be required to run Shor's algorithm on cryptographically relevant key sizes.

1.3 Quantum Algorithms

Two quantum algorithms are of particular concern to cryptography:

• Shor's Algorithm (1994): Efficiently factors large integers and computes discrete logarithms. This breaks RSA and ECC (Elliptic Curve Cryptography), as well as Diffie‑Hellman key exchange. The complexity of Shor's algorithm is polynomial, O((log N)³), making it feasible on a sufficiently large fault‑tolerant quantum computer.
• Grover's Algorithm (1996): Provides a quadratic speedup for unstructured search. For symmetric cryptography, Grover's algorithm reduces the effective key length by half (e.g., AES‑256 becomes equivalent to AES‑128 against a quantum attack). This is not a catastrophic break, but it means that symmetric keys need to be doubled to maintain security (e.g., AES‑128 becomes vulnerable, AES‑256 remains secure).

flowchart TB
    QC(["⚛️ QUANTUM Computing BASICS"])

    subgraph QUBIT["🔹 QUBIT"]
        direction TB
        Q1["|ψ⟩ = α|0⟩ + β|1⟩"]
        Q2["Superposition:
can be 0 and 1 simultaneously"]
        Q3["Measurement collapses to 0 or 1"]
        Q1 --- Q2 --- Q3
    end

    subgraph GATES["🔹 QUANTUM GATES (Unitary Ops)"]
        direction TB
        G1["Hadamard (H):
Creates superposition"]
        G2["Pauli-X, Y, Z:
Bit flips, phase shifts"]
        G3["CNOT:
Entanglement (controlled NOT)"]
        G1 --- G2 --- G3
    end

    subgraph ALGO["🔹 QUANTUM ALGORITHMS"]
        direction TB
        A1["Shor:
Factors integers → Breaks RSA, ECC"]
        A2["Grover:
Quadratic search → Weakens AES, SHA"]
        A1 --- A2
    end

    QC --> QUBIT
    QC --> GATES
    QC --> ALGO

    classDef mainNode fill:#1a6bb0,stroke:#0b2545,stroke-width:2px,color:#ffffff,font-weight:bold,font-size:14px
    classDef subNode fill:#f8faff,stroke:#1a6bb0,stroke-width:1.5px,color:#0b2545,font-size:12px
    classDef itemNode fill:#eaf2fd,stroke:#1a6bb0,stroke-width:1px,color:#0b2545,font-size:11px
    classDef groupStyle fill:#f2f7fc,stroke:#1a6bb0,stroke-width:1.5px,color:#0b2545,font-weight:bold

    class QC mainNode
    class Q1,Q2,Q3,G1,G2,G3,A1,A2 itemNode
    class QUBIT,GATES,ALGO groupStyle
            

Figure 1.1 — Overview of quantum Computing fundamentals: qubits, quantum gates, and quantum algorithms.

2. Security Implications

2.1 Cryptographic Risks

The advent of a cryptographically relevant quantum computer (CRQC) would have profound consequences:

• Public‑Key Infrastructure (PKI): RSA, ECC, and DSA digital signatures would be forgeable, and key exchange (Diffie‑Hellman, ECDH) would be broken. This would undermine the trust model of the internet, including TLS/HTTPS, code signing, email encryption (S/MIME, PGP), and certificate authorities.
• Secure communications: All encrypted data that has been intercepted and stored (e.g., VPN traffic, emails, encrypted files) could be decrypted retrospectively—the "harvest now, decrypt later" threat.
• Digital signatures: Authentication of software updates, firmware, and legal documents would be compromised.
• Blockchain and cryptocurrencies: Many blockchain systems rely on ECC signatures; a quantum computer could forge transactions and steal funds.

The timeline for the CRQC is uncertain, but many experts estimate 10–20 years. However, the "harvest now, decrypt later" threat is already a reality: adversaries can collect encrypted data today and decrypt it in the future. This means that data with long‑term sensitivity (e.g., classified documents, health records, trade secrets) should already be protected with quantum‑resistant algorithms.

2.2 Impact on Public‑Key Encryption

The impact on different cryptographic primitives varies:

• RSA: Vulnerable to Shor's algorithm. Key lengths up to 4096 bits would be broken.
• ECC (Elliptic Curve Cryptography): Vulnerable to Shor's algorithm (discrete log problem).
• Diffie‑Hellman (DH): Vulnerable to Shor's algorithm.
• AES‑128: Reduced to ~64 bits of security by Grover's algorithm (theoretically, though implementation details matter). AES‑256 remains secure, offering ~128 bits of security.
• SHA‑256: Grover's algorithm could reduce the complexity of finding collisions, but SHA‑256 remains practically secure with appropriate padding and hash lengths.
• Hash‑based signatures (e.g., XMSS, SPHINCS+): Believed to be quantum‑resistant.

3. Post‑Quantum Cryptography

3.1 Quantum‑Resistant Algorithms

Post‑quantum cryptography (PQC) refers to cryptographic algorithms that are believed to be secure against both classical and quantum attacks. These algorithms are based on mathematical problems that are hard for both classical and quantum computers. The main families are:

• Lattice‑based: Based on the hardness of finding short vectors in high‑dimensional lattices. Examples: Kyber (key encapsulation), Dilithium (digital signatures). These are the leading candidates for standardization due to their efficiency and security.
• Code‑based: Based on the hardness of decoding random linear codes. Example: McEliece (encryption) – one of the oldest PQC schemes, with very large key sizes.
• Hash‑based: Based on the security of cryptographic hash functions. Examples: XMSS (stateful), SPHINCS+ (stateless). These are primarily used for digital signatures.
• Multivariate‑based: Based on the hardness of solving systems of multivariate equations. Example: Rainbow (signatures) – though Rainbow was broken in 2022, highlighting the need for careful analysis.
• Isogeny‑based: Based on the hardness of finding isogenies between elliptic curves. Example: SIKE (key encapsulation) – also broken in 2022, demonstrating the fragility of some PQC proposals.

The NIST PQC Standardization Process has been running since 2016. In 2022, NIST announced the first standardized algorithms:

• CRYSTALS‑Kyber: Key encapsulation mechanism (KEM) – standard as ML‑KEM.
• CRYSTALS‑Dilithium: Digital signature – standard as ML‑DSA.
• SPHINCS+: Hash‑based signature – standard as SLH‑DSA.
• Falcon: Lattice‑based signature – standard as FN‑DSA.

These algorithms are now available for implementation and are expected to be widely adopted in the coming years.

3.2 Migration Strategies

Migrating to post‑quantum cryptography is a complex, multi‑year process. Key strategies include:

• Hybrid Cryptography: Combining classical and post‑quantum algorithms in a single cryptographic protocol. For example, a TLS connection could use both ECDH (classical) and ML‑KEM (post‑quantum) key exchange. The security of the hybrid is at least as strong as the strongest of the two components. This provides a gradual migration path and ensures backward compatibility.
• Crypto‑Agility: Designing systems to support multiple cryptographic algorithms and to switch between them easily. This requires modular architecture, configuration‑driven algorithm selection, and automated testing.
• Priority‑based migration: Not all systems need to be migrated at once. Prioritization should be based on data sensitivity, system lifespan, and the exposure of the cryptographic material. For example, systems protecting long‑term secrets (e.g., certificate authorities, VPN concentrators) should be migrated first.
• Testing and validation: Extensive testing is required to ensure that PQC implementations are correct, efficient, and secure. This includes performance testing, compatibility testing, and security evaluation.

3.3 Future Cryptographic Planning

Organizations should adopt a post‑quantum roadmap that includes:

• Inventory: Understanding where and how cryptography is used.
• Assessment: Evaluating the quantum risk for each use case.
• Planning: Developing a migration plan with clear milestones.
• Implementation: Deploying PQC in phases, starting with pilot projects.
• Verification: Continuously validating the security and performance of PQC deployments.

4. Organizational Readiness

4.1 Crypto Inventory

A crypto inventory is a comprehensive catalog of all cryptographic assets and their usage within an organization. This is the foundational step for post‑quantum readiness. The inventory should include:

• Assets: Systems, applications, devices, and data that use cryptography.
• Cryptographic algorithms: Which algorithms are in use (RSA, ECC, AES, SHA, etc.) and their key lengths.
• Protocols: Which protocols use cryptography (TLS, IPSec, SSH, S/MIME, etc.).
• Key management: Where are keys stored, how are they generated, and what are their lifecycles?
• Dependencies: Which systems depend on the cryptographic infrastructure (e.g., certificate authorities, HSMs).
• Data sensitivity: Which data needs long‑term confidentiality and is vulnerable to the "harvest now, decrypt later" threat.

Conducting a crypto inventory is a significant undertaking, but it is essential for understanding the scope of the migration effort. Automated discovery tools can help identify cryptographic assets, but manual verification is often required for legacy systems.

4.2 Transition Planning

A post‑quantum transition plan should be developed with the following phases:

• Phase 1: Awareness and Assessment (0–1 year)
  – Build awareness of the quantum threat across the organization.
  – Conduct a crypto inventory and risk assessment.
  – Identify high‑priority systems for migration.
• Phase 2: Pilot and Testing (1–2 years)
  – Pilot PQC in non‑critical systems.
  – Test hybrid TLS configurations.
  – Evaluate performance and compatibility.
• Phase 3: Migration of High‑Risk Systems (2–5 years)
  – Migrate certificate authorities, VPNs, and other critical systems.
  – Implement crypto‑agile architectures.
  – Begin using PQC for long‑term data protection.
• Phase 4: Full Deployment (5–10 years)
  – Migrate all remaining systems.
  – Decommission vulnerable classical algorithms.
  – Continuous monitoring and updates.

flowchart TB
    P1["📋 Phase 1
Awareness & Assessment
(0–1 year)
• Educate stakeholders
• Complete crypto inventory
• Assess quantum risk"]
    P2["🧪 Phase 2
Pilot & Testing
(1–2 years)
• Deploy PQC in test environments
• Test hybrid crypto
• Validate performance"]
    P3["🚀 Phase 3
Migration
(2–5 years)
• Migrate CAs, VPNs, secure storage
• Implement crypto-agility
• Deploy PQC for long-term data"]
    P4["✅ Phase 4
Full Deployment
(5–10 years)
• Complete migration of all systems
• Decommission classical algorithms
• Continuous monitoring"]

    P1 --> P2 --> P3 --> P4

    classDef phase1 fill:#eaf2fd,stroke:#1a6bb0,stroke-width:1.5px,color:#0b2545
    classDef phase2 fill:#d9e8fa,stroke:#1a6bb0,stroke-width:1.5px,color:#0b2545
    classDef phase3 fill:#c6dcf5,stroke:#1a6bb0,stroke-width:1.5px,color:#0b2545
    classDef phase4 fill:#a9c9ee,stroke:#1a6bb0,stroke-width:1.5px,color:#0b2545

    class P1 phase1
    class P2 phase2
    class P3 phase3
    class P4 phase4
            

Figure 4.1 — Post-quantum transition roadmap: a phased, multi-year migration strategy.