After completing this tutorial, you will be able to:
Quantum computing represents one of the most profound technological shifts since the invention of the transistor. While still in its early stages, quantum computers have the potential to solve problems that are intractable for classical computers, with profound implications for cryptography, optimization, and simulation. For cybersecurity, the most significant concern is the cryptographic threat: quantum computers running Shor's algorithm can factor large numbers and compute discrete logarithms in polynomial time, effectively breaking RSA, ECC, and Diffie‑Hellman—the foundations of modern public‑key infrastructure (PKI).
The timeline for the emergence of a cryptographically relevant quantum computer (CRQC) is debated, but many experts estimate that it could arrive within the next 10–20 years. This means that the data being encrypted today with classical algorithms may be vulnerable to "harvest now, decrypt later" attacks, where adversaries collect encrypted data now and decrypt it once quantum computers become available. This creates an urgent need for organizations to begin their transition to post‑quantum cryptography (PQC)—cryptographic algorithms that are resistant to both classical and quantum attacks.
This tutorial, Tutorial 8.13: Quantum Computing and Post‑Quantum Security, provides a comprehensive overview of the quantum threat and the steps organizations must take to prepare. We begin with the fundamentals of quantum computing, explaining the key concepts—qubits, superposition, entanglement, and quantum gates—that underpin quantum algorithms. We then describe the two most important quantum algorithms for cryptography: Shor's algorithm (which breaks public‑key cryptography) and Grover's algorithm (which weakens symmetric cryptography).
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.
Quantum computing harnesses the principles of quantum mechanics to perform computations. Two key principles are:
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).
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.
Two quantum algorithms are of particular concern to cryptography:
| Algorithm | Function | Cryptographic Impact | Complexity (Quantum) |
|---|---|---|---|
| Shor's Algorithm | Integer factorization, discrete log | Breaks RSA, ECC, DSA, DH | Polynomial: O((log N)³) |
| Grover's Algorithm | Unstructured search | Weakens symmetric crypto (AES, SHA) | Quadratic speedup: O(√N) |
The advent of a cryptographically relevant quantum computer (CRQC) would have profound consequences:
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.
The impact on different cryptographic primitives varies:
In 2023, intelligence agencies in multiple countries were reported to be collecting large volumes of encrypted internet traffic, storing it for future decryption once quantum computers become available. This practice, known as "harvest now, decrypt later," highlights the urgency of transitioning to post‑quantum cryptography. Any data that is encrypted today with RSA or ECC could be exposed in the future, including:
This threat has driven the accelerated adoption of post‑quantum cryptography in some sectors, with organizations like Google, Cloudflare, and IBM already deploying hybrid PQC in their products.
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:
The NIST PQC Standardization Process has been running since 2016. In 2022, NIST announced the first standardized algorithms:
These algorithms are now available for implementation and are expected to be widely adopted in the coming years.
| Family | Algorithm (NIST Standard) | Type | Key Size | Performance |
|---|---|---|---|---|
| Lattice‑based | ML‑KEM (Kyber) | KEM | ~1.5 KB public key | Fast, practical |
| Lattice‑based | ML‑DSA (Dilithium) | Signature | ~1.3 KB public key | Fast, practical |
| Hash‑based | SLH‑DSA (SPHINCS+) | Signature | ~1 KB public key | Slower, larger signatures |
| Lattice‑based | FN‑DSA (Falcon) | Signature | ~1 KB public key | Very fast, complex implementation |
Migrating to post‑quantum cryptography is a complex, multi‑year process. Key strategies include:
Organizations should adopt a post‑quantum roadmap that includes:
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:
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.
A post‑quantum transition plan should be developed with the following phases:
In 2024, Google announced that it had deployed a hybrid post‑quantum key exchange (X25519Kyber768) in its Chrome browser and on its internal networks. This represented one of the first large‑scale deployments of PQC in a consumer product. Google's approach:
Lessons: Hybrid cryptography is a practical way to begin the transition. Performance impact is minimal with modern implementations. Early adoption builds experience and confidence for broader deployments.
Answer the following questions to test your understanding. Click each "Answer" summary to reveal the solution.
A qubit is a quantum bit that can exist in a superposition of states |0⟩ and |1⟩, represented as α|0⟩ + β|1⟩. Unlike a classical bit, which is either 0 or 1, a qubit can be in both states simultaneously, enabling parallel computation.
Shor's algorithm efficiently factors large integers and computes discrete logarithms in polynomial time. It threatens public‑key cryptography, including RSA, ECC, and Diffie‑Hellman.
Grover's algorithm provides a quadratic speedup for unstructured search, reducing the effective key length of symmetric algorithms by half. For example, AES‑128 becomes roughly equivalent to 64‑bit security against a quantum attack.
Adversaries can collect encrypted data today and store it until a cryptographically relevant quantum computer becomes available, at which point they can decrypt it. This threatens long‑term data confidentiality.
ML‑KEM (Kyber) – key encapsulation mechanism.
ML‑DSA (Dilithium) – digital signature.
SLH‑DSA (SPHINCS+) – hash‑based signature.
FN‑DSA (Falcon) – lattice‑based signature.
Hybrid cryptography combines classical and post‑quantum algorithms in a single protocol. This provides security against both types of attacks and enables a gradual migration while maintaining backward compatibility.
Crypto‑agility is the ability to switch between cryptographic algorithms easily, without significant system redesign. It is important for the PQC transition and for adapting to future cryptographic changes.
A crypto inventory is a catalog of all cryptographic assets and their usage within an organization. It is essential for understanding the scope of the migration effort and for identifying high‑priority systems.
Lattice‑based, code‑based, hash‑based, multivariate‑based (with caution), and isogeny‑based (with caution) are the main families of quantum‑resistant cryptography.
Grover's algorithm reduces the effective security of symmetric encryption by half. AES‑128 becomes ~64‑bit security, which is vulnerable. AES‑256 becomes ~128‑bit security, which is still considered secure.
Estimates vary widely, but many experts predict that a CRQC could emerge within 10–20 years. However, the "harvest now, decrypt later" threat is already relevant.
The first step is to conduct a crypto inventory to understand where and how cryptography is used, followed by a risk assessment to prioritize systems for migration.
These practical exercises will help you apply the concepts. Suggested solutions are hidden beneath each exercise.
Fields:
1. System/Application Name – identifies the asset.
2. Owner/Contact – responsible person.
3. Cryptographic Algorithm – RSA, ECC, AES, SHA, etc.
4. Key Length – e.g., RSA‑2048, ECC‑P256.
5. Protocol – TLS, IPSec, SSH, S/MIME, etc.
6. Data Sensitivity – High/Medium/Low (based on
data classification).
7. Data Retention Period – how long data must be
protected.
8. Quantum Risk – High/Medium/Low (based on
algorithm and key length).
9. Migration Priority – P1 (critical), P2 (medium),
P3 (low).
10. Migration Status – Not Started, In Progress,
Completed.
Justification: These fields provide a comprehensive
view of the cryptographic landscape, enabling risk assessment and
prioritization.
Configuration:
- Use a version of OpenSSL (or a fork like BoringSSL) that supports
hybrid groups.
- Enable the hybrid group `X25519Kyber768` (or `X25519Kyber512`
for lower security).
- In the server configuration, set the cipher suite to include
hybrid suites: `ECDHE‑KYBER‑AES256‑GCM‑SHA384` or similar.
- Use a configuration like: `ssl_ciphers "ECDHE+KYBER:AES256‑GCM‑SHA384";`
- Ensure that clients also support the hybrid group; fallback to
classical if they do not.
- Test the configuration with tools like `openssl s_client` to verify
the negotiated cipher suite.
Risk Assessment:
- RSA‑2048 is vulnerable to Shor's algorithm.
- A CRQC is expected within 10‑20 years.
- Data retention of 10 years means it will be at risk during the
latter part of its retention period.
- The "harvest now, decrypt later" threat applies: attackers could
collect data now and decrypt it later.
Migration Strategy:
- Short‑term: Use hybrid encryption (RSA + ML‑KEM)
for new data, while maintaining RSA for backward compatibility.
- Medium‑term: Migrate to ML‑KEM for key exchange
and ML‑DSA for signatures.
- Long‑term: Migrate all data to PQC and phase out
RSA.
- Priority: High, due to long‑term data sensitivity.
ML‑KEM (Kyber): Efficient key encapsulation with
moderate key sizes (1.5 KB). Suitable for key exchange.
SLH‑DSA (SPHINCS+): Stateless hash‑based signature
with large signatures (tens of KB) and slower performance. Not ideal
for resource‑constrained devices.
ML‑DSA (Dilithium): Lattice‑based signature with
moderate key sizes (1.3 KB) and fast signing/verification. Suitable
for signatures.
Recommendation: For key exchange, use ML‑KEM
for its efficiency. For signatures, use ML‑DSA if
the device can handle the computational load. Avoid SLH‑DSA for
constrained devices due to large signatures.
Year 1: Discovery & Assessment
- Complete crypto inventory.
- Assess quantum risk for all systems.
- Establish a PQC steering committee.
Year 2: Pilot & Foundation
- Pilot PQC in non‑critical systems (test environments).
- Implement crypto‑agile frameworks.
- Train security and engineering teams.
Year 3: Migration of Critical Systems
- Migrate certificate authorities to ML‑DSA.
- Deploy hybrid TLS for external‑facing applications.
- Migrate VPN and remote access systems.
Year 4: Broader Deployment
- Migrate internal applications and services.
- Implement PQC for data at rest (storage encryption).
- Monitor performance and address issues.
Year 5: Completion & Decommission
- Complete migration of all remaining systems.
- Decommission vulnerable algorithms (RSA, ECC).
- Conduct final security audit.
Success Criteria: All systems using PQC or hybrid
crypto; no systems relying solely on vulnerable classical algorithms;
successful audit.
These assignments require research, analysis, and synthesis. Use external resources to support your responses.
A strong paper would:
– Explain quantum computing using accessible analogies.
– Describe the current state (NISQ devices) and the challenges
(error correction, scalability).
– Discuss the timeline: many experts predict 10‑20 years for a
CRQC, but some argue it could be sooner or later.
– Emphasize that the "harvest now, decrypt later" threat is
already a concern.
– Include references to industry reports (e.g., McKinsey, NIST).
A strong report would:
– Trace the NIST PQC process from its launch in 2016 to the
2022 announcements.
– Describe the selected algorithms (ML‑KEM, ML‑DSA, SLH‑DSA,
FN‑DSA) and their mathematical foundations.
– Discuss the security and performance trade‑offs.
– Explain the rationale for selecting lattice‑based and hash‑based
candidates.
– Discuss the next steps: adoption, standardization, and
deployment guidance.
A strong analysis would:
– Explain how blockchain relies on ECC for digital signatures.
– Assess the quantum risk: a CRQC could steal funds by forging
signatures.
– Discuss the timeline: most estimates suggest 5‑10 years before
quantum attacks on blockchain are feasible.
– Review solutions: quantum‑resistant blockchains, hybrid
approaches, and the challenges of upgrading existing blockchains.
– Provide a risk assessment and recommendations for cryptocurrency
holders and developers.
A strong guide would:
– Provide step‑by‑step instructions for enabling hybrid TLS
(e.g., using BoringSSL or a PQC‑enabled OpenSSL).
– Explain how to use the NIST‑standardized algorithms in code
(e.g., using liboqs).
– Discuss key management: key generation, storage, and rotation
for PQC keys.
– Address the performance implications and provide optimization
tips.
– Include code examples and references to libraries.
A strong paper would:
– Discuss the projected timeline for CRQC and the uncertainty
involved.
– Explain quantum key distribution (QKD) and its strengths and
limitations (distance, cost, practical challenges).
– Compare PQC and QKD: PQC is a cryptographic solution, QKD is
a physical solution. They are complementary.
– Discuss the concept of "quantum‑safe" cryptography and the
need for a layered approach.
– Explore the implications for national security, data privacy,
and international standards.
– Propose a research agenda for the next decade.
Tutorial 8.13 has provided a comprehensive overview of quantum computing and post‑quantum security. We began with the fundamentals of quantum computing, explaining the key concepts—qubits, superposition, entanglement, and quantum gates—that enable quantum algorithms. We discussed Shor's algorithm, which breaks public‑key cryptography, and Grover's algorithm, which weakens symmetric cryptography.
We then analyzed the security implications: the vulnerability of RSA, ECC, and Diffie‑Hellman to quantum attacks, and the "harvest now, decrypt later" threat that makes long‑term data vulnerable today. We emphasized that the timeline for a cryptographically relevant quantum computer may be 10‑20 years, but the risk is already real for data that must remain confidential for decades.
The core of the tutorial was dedicated to post‑quantum cryptography. We surveyed the main families of quantum‑resistant algorithms—lattice‑based, code‑based, hash‑based, and multivariate—and reviewed the NIST‑standardized algorithms: ML‑KEM (Kyber), ML‑DSA (Dilithium), SLH‑DSA (SPHINCS+), and FN‑DSA (Falcon). We discussed migration strategies, including hybrid cryptography and crypto‑agility, and the importance of a phased, risk‑based approach.
Finally, we addressed organizational readiness: the need for a comprehensive crypto inventory, a risk assessment, and a detailed transition plan. We provided a roadmap for the next 5‑10 years, emphasizing that the transition to post‑quantum cryptography is not a single event but a journey that requires proactive planning, investment, and collaboration across the organization.
This tutorial prepares you for the quantum future. Whether you are a security architect, a CISO, or a researcher, the knowledge and strategies covered here will be essential for protecting your organization's data in the post‑quantum era.