Quantum Computing

Quantum computers leverage quantum mechanics to solve certain mathematical problems exponentially faster than classical computers. Algorithms like Shor’s could render widely used cryptographic methods such as RSA and Elliptic Curve Cryptography obsolete. Experts suggest that the first quantum-enabled cryptographic breaches might occur as early as 2030 posing a serious threat to global information infrastructure.

Almost everything you do on a computer today relies on cryptography from protecting emails and medical records to safeguarding financial transactions and critical infrastructure. Modern encryption methods like 2048-bit public keys are incredibly secure but their robustness could be shattered by the advent of large-scale quantum computing.

To counter this researchers and organizations are developing quantum-safe or post-quantum cryptography (PQC) algorithms that resist attacks from both classical and quantum computers. The U.S. National Institute of Standards and Technology (NIST) has taken a leading role in standardizing these next-generation cryptographic solutions releasing its first three post-quantum cryptography standards in August 2024. While symmetric cryptographic algorithms can largely withstand quantum threats with minor adjustments public-key cryptography demands a complete overhaul to remain secure.

Quantum-safe cryptography secures sensitive data, access and communications for the era of quantum computing.

Post-Quantum Cryptography (PQC) and Standardization Efforts

Recognizing the urgency of the quantum threat the National Institute of Standards and Technology (NIST) initiated a global effort to standardize post-quantum cryptographic (PQC) algorithms. After a multi year evaluation process NIST announced its first set of post quantum cryptographic standards in August 2024 by selecting algorithms designed to withstand both classical and quantum attacks.

NIST’s Selected Algorithms for PQC

NIST has chosen three primary algorithms for standardization:

1. CRYSTALS Kyber– A key encapsulation mechanism (KEM) for secure communication.
2. CRYSTALS Dilithium – A digital signature algorithm providing authentication.
3. SPHINCS+ – A stateless hash-based signature scheme for enhanced security

But before diving deep into it let’s explore Quantum safe Cryptographic approaches.

Quantum-Safe Cryptographic Approaches

The field of post-quantum cryptography (PQC) explores various approaches to building quantum-resistant encryption methods:

1. Lattice-Based Cryptography

Lattice-based cryptography is a major area of post-quantum cryptography relying on the difficulty of problems related to mathematical structures called lattices. A lattice is a regular arrangement of points in space. These problems include finding the shortest vector (SVP) or the closest vector (CVP) within the lattice. A prominent example is the Learning With Errors (LWE) problem.

How it Works?

1. Key Generation:

   • Choose a random matrix A (size m x n).
   • Choose a secret vector s.
   • Choose a small noise vector e.
   • Compute the public key b = A * s + e.
   • The secret key is s, and the public key is (A, b).

2. Encryption:

   • To encrypt a message m, represent it as a vector.
   • Choose a random vector r.
   • Compute u = AT * r.
   • Compute v = bT * r + m.
   • The ciphertext is (u, v).

3. Decryption:

   • Compute v - sT * u.
   • This removes the noise and recovers the message m.

Example:

Let’s use a very simplified (and insecure) example to show the principles (using modulo 5 arithmetic for simplicity).

1. Key Generation:

   A = [[2, 1], [4, 3]]
   s = [3, 1]
   e = [1, 2]
   b = [4, 2] (modulo 5)

2. Encryption:

   m = [1, 0]
   r = [1, 2]
   u = [0, 2] (modulo 5)
   v = [4, 4] (modulo 5)

3. Decryption :

   v = b^T * r + m
   b^T * r = 2 (mod 5)
   v = 2 + m + noise
   [4, 4] = 2 + [1, 0] + [1, 4] (noise)
   [4, 4] - 2 = [2, 4]
   [2, 4] - [1, 4] (noise) = [1, 0]

Result:

m' = [1, 0] Therefore, the correct decryption recovers the original message m = [1, 0].

Why it’s Secure?

The security of LWE is based on the conjecture that it is difficult to solve even for quantum computers. While related to NP-hard problems the quantum resistance of LWE isn’t simply due to NP-hardness (as some NP-hard problems might be solvable by quantum computers). Rather, the specific structure of lattice problems and LWE makes them resistant to known quantum algorithms like Shor’s algorithm. Practical cryptographic schemes often use variants like Module-LWE (MLWE) for improved efficiency.

2. Hash-Based Cryptography

Hash-based cryptography avoids number-theoretic problems (like factoring or discrete logarithms) that quantum computers might be able to solve. Instead, it leverages the one-wayness and collision resistance of cryptographic hash functions. A prominent example is SPHINCS+, a post-quantum signature scheme.

How it Works?

1. Secret Key: You choose a random secret value S.
2. Public Key: You apply a cryptographic hash function H multiple times to S. For example:
   • H(S)
   • H(H(S))
   • H(H(H(S)))
   • and so on, a certain number of times. The final result is your public key PK.
3. Signing: To sign a message M, you use your secret key S and some of the intermediate hash values (parts of the “hash chain”) to create a signature. The process involves hashing the message M combined with portions of the hash chain.
4. Verification: Someone with your public key PK can verify the signature. They recompute the hashes using the provided parts of the hash chain and the message M. If the final hash matches the published public key PK, the signature is valid.

Example:

Let’s imagine a very simplified hash function H(x) = x² mod 100. (This is not cryptographically secure, but just for understanding).

• S (secret) = 3
• PK = H(H(H(S))) = H(H(9 mod 100)) = H(81 mod 100) = 6561 mod 100 = 61. So, PK = 61.

Now signing and verification would involve using S and some intermediate hash values (in a more complex scheme) along with the message. The point is that given 61 it’s hard to find 3 (even in this example it would take some trial and error). A real cryptographic hash function makes this computationally infeasible.

Why it’s Secure:

• One-Wayness: It’s computationally infeasible to go from the public key PK (the final hash) back to the secret key S because of the one-way property of the hash function.
• Collision Resistance: It’s extremely difficult to find two different messages that hash to the same value. This prevents someone from forging a signature for a different message.

3. Code-Based Cryptography

The McEliece cryptosystem uses the difficulty of decoding a randomly perturbed linear code. While decoding a general linear code is known to be NP-hard. Decoding specific structured codes (like Goppa codes) can be done efficiently. The system hides the structure of a good code by disguising it as a general hard-to-decode code.

How it Works?

1. Secret Key: Choose a secret Goppa code (a type of error-correcting code with efficient decoding algorithms).

   • Generate a generator matrix G for this Goppa code.
   • Select a random invertible matrix S.
   • Select a random permutation matrix P.

2. Public Key: Compute the public key as PK = SGP. This disguises the structure of the Goppa code.

3. Encryption: To encrypt a message m, represent it as a binary vector.

   • Generate a random error vector e with a specific weight (number of 1s).
   • Compute the ciphertext as c = mPK + e.

4. Decryption: The receiver knowing S, G, and P, can:

   • Compute c’ = cP⁻¹ = mSG + eP⁻¹.
   • Compute c’’ = S⁻¹c’ = mG + S⁻¹eP⁻¹.
   • Use the efficient decoding algorithm for the Goppa code (represented by G) to recover m.
   • Multiply by S to get the original message.

Example:

Let’s use a very simplified (and insecure) example to show the principles:

1. Secret Key: Goppa code (simplified): Let’s say our Goppa code allows us to correct one error.

   • G (generator matrix, very small for simplicity): [[1, 0, 1], [0, 1, 1]]
   • S (invertible matrix): [[1, 1], [0, 1]]
   • P (permutation matrix): [[0, 1, 0], [0, 0, 1], [1, 0, 0]]

2. Public Key: PK = SGP: [[1, 1, 0], [1, 1, 1]]

3. Encryption: Message m = [1, 0]

   • Error e = [0, 0, 1]
   • Ciphertext c = mPK + e: [1, 1, 0] + [0, 0, 1] = [1, 1, 1]

4. Decryption:

   • c’ = cP⁻¹: [1, 1, 1]
   • c’’ = S⁻¹c’: [0, 1, 1]
   • Using the Goppa code’s decoding we can recover m = [1, 0].

Why Secure?

• NP-Hardness: Decoding a general linear code is NP-hard. This means that finding a general solution is computationally infeasible for large codes.
• Goppa Code Structure: The public key PK hides the structure of the efficient Goppa code. Only someone with the secret key can efficiently decode the ciphertext.
• Random Perturbation: The random matrices S and P “perturb” the Goppa code, making it appear as a random, general linear code further increasing the difficulty for an attacker.
• Resistance to Quantum Attacks: While quantum computers can solve some NP-hard problems there are no known efficient quantum algorithms that can break the McEliece cryptosystem. Therefore it is considered quantum resistant.

Now we have explored the Quantum Safe Cryptographic Approaches let’s dive deep into the NIST selected Algorithms & try to understand their working principles mathematically.

CRYSTALS-Kyber (Key Encapsulation Mechanism):

• Kyber is based on the Module Learning With Errors (MLWE) problem over rings. This involves operations with matrices and vectors of polynomials.
• The security parameters (matrix dimensions, polynomial coefficients) are crucial and must be chosen carefully to maintain adequate security margins.
• Kyber is known for its relatively efficient key generation, encapsulation and decapsulation processes. This makes it a practical choice for many applications.
• The use of polynomial rings and operations within them is a core part of Kyber’s design. This adds complexity compared to simple integer-based cryptography.
• The careful addition and management of “noise” (error polynomials) is essential for Kyber’s security. Improper noise distributions or magnitudes can weaken the system.
• Kyber was selected by NIST for standardization indicating its strong security and performance properties.

Concept :

• Imagine a scenario where you have a “noisy” system of linear equations but instead of numbers the coefficients and variables are polynomials.
• The secret key involves a set of these polynomial vectors.
• The public key is derived by multiplying these secret vectors with random polynomial matrices and adding “noise” (small error polynomials).
• Encryption involves using the public key to create another noisy system of polynomial equations.
• Decryption relies on the ability to “decode” the message by removing the noise which is computationally difficult without the secret key.
• It is very hard to recreate the original secret key from the public key because of the noise that is added.

Example (Modulo 5 Polynomials)

(Simplified example for understanding purpose)

• Polynomial Ring:

  • Coefficients: {0, 1, 2, 3, 4}
  • Example Polynomials: 2x + 1, 3x² + 4x + 2

• Secret Key (s):

  • s = [x + 2, 3x + 1]

• Public Key Generation:

  • Random Matrix (A): A = [[2x, x + 1], [4, 3x]]
  • Noise Vector (e): e = [1, 2x]
  • Public Key (b): b = A \* s + e
  • b = [[2x, x + 1], [4, 3x]] \* [x + 2, 3x + 1] + [1, 2x]
  • b = [4x² + 2x + 1, 2x² + 3x + 2] (simplified result)

• Encryption (Simplified):

  • Message (m): m = x
  • Random Vector (r): r = [1, x]
  • u = AT * r
  • u = [[2x, 4], [x+1, 3x]] \* [1, x]
  • u = [2x+4x, x+1+3x²]
  • u = [4x+2x, 3x²+x+1]
  • v = bT * r + m
  • v = [4x² + 2x + 1, 2x² + 3x + 2] \* [1, x] + x
  • v = 4x²+2x+1 + x(2x³+3x²+2x) + x
  • v = 4x²+2x+1 + 2x³+3x²+2x + x
  • v = 2x³+7x²+5x+1
  • v = 2x³+2x²+1 (modulo 5)
  • Ciphertext: (u, v) = ([4x+2x, 3x²+x+1], 2x³+2x²+1)

• Decryption:

  • We know: v = b<sup>T</sup> \* r + m, and b = A \* s + e.
  • Therefore: v = (A \* s + e)<sup>T</sup> \* r + m
  • v = (sT * AT + eT) * r + m
  • v = sT * u + eT * r + m
  • To recover m, compute: m = v - sT * u - eT * r
  • m = (2x³+2x²+1) - [x+2, 3x+1] * [4x+2x, 3x²+x+1] - [1, 2x] * [1, x]

By performing polynomial multiplications and subtractions (modulo 5) the goal is to cancel the noise (eT * r) and retrieve the original message (m). The “noise” (e) is crucial. It makes it difficult to recover the secret key (s) from the public key (b). The operations are performed in a polynomial ring which adds complexity.

Notes

• This example uses tiny parameters and modulo 5 (for understanding purpose).
• It employs simplified polynomial math to show the core idea.
• It uses basic noise vectors and encryption/decryption (not cryptographically sound).
• This example only shows the very basic idea of how MLWE is used.

Key Math Concepts

• Lattice theory
• Polynomial rings
• Module theory

CRYSTALS-Dilithium (Digital Signature Algorithm)**

• Dilithium provides digital signatures based on the Module-Short-Integer-Solution (MSIS) problem another lattice-based problem.This offers strong authentication capabilities in a post-quantum environment.
• The security of Dilithium rests on the assumption that finding short vectors in certain lattices is computationally difficult.
• Dilithium is designed to be efficient for signature generation and verification making it suitable for various applications.
• Understanding the MSIS problem and the underlying lattice structures is essential for evaluating Dilithium’s security.
• Dilithium relies on cryptographic hash functions for message integrity and randomness. The choice of hash function is crucial for overall security.
• Dilithium was also selected by NIST for standardization confirming its robustness and suitability for widespread use.

Concept

• Imagine a high-dimensional grid (lattice).
• Secret key: “short” vectors within this lattice.
• Public key: derived from the secret vectors.
• Signing: finding a new short vector related to the hashed message.
• Verification: checking if the signature vector is short and consistent with the public key and message.

Example

(Simplified example for understanding purpose)

• Vectors and matrices of small integers modulo a small prime.

• Secret Key:

  • s1 = [1, -1]
  • s2 = [0, 2]

• Public Key:

  • Random matrix A = [[3, 1], [2, 4]].
  • Public key t = A * s1 + s2 = [[3, 1], [2, 4]] * [1, -1] + [0, 2] = [2, 0].

• Signing (Very Simplified):

  • Hashed message leads to y = [1, 1].
  • Find short vector z such that z * A is close to y.
  • Random vector r = [1, 0].
  • z = r + s1 = [2, -1]. (Signature)

• Verification (Very Simplified):

  • z * A = [2, -1] * [[3, 1], [2, 4]] = [4, -2].
  • Check if [4, -2] is related to the message and public key.

Notes

• This example uses tiny vectors and small matrices (for understanding purpose).
• It employs basic integer math to show the MSIS concept.
• It uses simplified “short” vectors and a basic signing/verification process (not cryptographically sound).
• This example only shows the very basic idea of how lattice-based signatures work.

Key Math Concepts

• Lattice theory
• Linear algebra
• Hash functions
• Modular Arithmetic.
• Norms.

These algorithms are based on mathematical problems believed to be resistant to quantum attacks, ensuring long-term security in a post-quantum world

SPHINCS+ (Hash-Based Signature Scheme)

• SPHINCS+ is unique in that it relies solely on the security of cryptographic hash functions. This makes it resistant to quantum attacks without depending on number-theoretic assumptions.
• It’s a stateless signature scheme meaning it doesn’t require maintaining internal state between signature generations. This simplifies implementation and reduces the risk of security vulnerabilities related to state management.
• SPHINCS+ uses Merkle trees to efficiently compress and verify signatures. Understanding how Merkle trees work is crucial for understanding the scheme’s operation.
• The security of SPHINCS+ is directly tied to the strength of the underlying hash function. It’s designed to be flexible and can be instantiated with different hash functions (e.g., SHAKE256).
• SPHINCS+ provides forward security meaning that even if a secret key is compromised previously generated signatures remain valid.
• Signature generation can be computationally expensive particularly for large messages. Verification is relatively efficient.
• SPHINCS+ was selected by NIST for standardization highlighting its robustness and security properties.

Concept

• Tree-like structure with hash values at each node (Merkle tree).
• Secret key: initial random values.
• Public key: root of the hash tree.
• Signing: revealing branches of the hash tree for verification.
• Security: relies on one-wayness and collision resistance of hash functions.

Example

• Let’s use a very simple (and insecure) hash function for understanding purpose: H(x) = x^2 mod 10.

• Secret Key:

  • Initial values: S1 = 3, S2 = 5.

• Public Key:

  • Build a simplified Merkle tree:
    • Node1 = H(S1) = 9
    • Node2 = H(S2) = 5
    • Root (Public Key) = H(Node1 + Node2) = H(14) = 4

• Signing (Very Simplified):

  • To sign a message reveal parts of the path to the root.
  • Let’s say the signing process needs to reveal S1. The signature will contain S1 and any other needed information to verify the path to the root.
  • Signature =(3, Node2)

• Verification (Very Simplified):

  • Given the signature (3, 5) and the public key (4), verify:
  • H(3) = 9
  • H(5) = 5
  • H(9 + 5) = H(14) = 4 (Matches the public key).

Key Math Concepts

• Cryptographic hash functions (one-way, collision-resistant)
• Merkle trees (for efficient verification)
• One-way functions (essential for security)

Notes

• Real SPHINCS+ uses cryptographically secure hash functions (e.g., SHAKE256).
• It employs complex Merkle tree structures for security.
• It uses techniques to prevent key reuse and provide forward security.
• This example only shows the very basic idea of how hash chains are used.

Mathematical Comparison: NIST Quantum-Safe vs. Traditional Cryptographic Algorithms

To understand the impact of post-quantum cryptography (PQC), we can compare NIST-selected quantum-safe algorithms against traditional cryptographic methods based on key factors. This includes key size, which affects storage and transmission efficiency, signature size and efficiency, which influence authentication performance, computational cost, determining encryption and decryption speed, and security level, measuring resistance against both classical and quantum attacks. Below, we break down these aspects to highlight the differences and advantages of quantum-safe cryptographic algorithms.

---

1. Key Size Comparison

Key size determines how difficult it is to break an encryption scheme. Classical algorithms rely on the difficulty of factoring large numbers or discrete logarithm problems which quantum algorithms like Shor’s can break efficiently.

Algorithm	Key Size (bytes)
RSA-3072	384
ECC P-256	32
X25519 (ECDH)	32
AES-256	32
CRYSTALS-Kyber-512	800
CRYSTALS-Kyber-768	1,184
CRYSTALS-Kyber-1024	1,568

• Kyber (NIST PQC standard) requires significantly larger key sizes than RSA/ECC but remains efficient due to lattice-based optimizations.
• Kyber-512 (~800 bytes) is considered equivalent to RSA-3072 (~384 bytes) in security but offers post-quantum resilience.

---

2. Signature Size & Efficiency

Digital signatures are crucial for authentication. Quantum-safe signatures are generally larger than traditional ones but offer better security.

Algorithm	Public Key (bytes)	Signature (bytes)
ECDSA P-256	64	64
RSA-3072	384	384
CRYSTALS-Dilithium-5	2,528	4,595
SPHINCS+-256s	2,128	29,000

• Dilithium provides strong post-quantum security with moderate key and signature sizes.
• SPHINCS+ has a very large signature size (up to 29 KB) but offers strong security using hash-based cryptography.

---

3. Computational Cost (Encryption & Decryption Complexity)

Let’s compare the time complexity of encryption and decryption operations.

Algorithm	Encryption Complexity	Decryption Complexity
RSA-3072	𝑂(𝑛³)	𝑂(𝑛³)
ECC P-256	𝑂(𝑛²)	𝑂(𝑛²)
Kyber-512	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)
Dilithium-2	𝑂(𝑛²)	𝑂(𝑛²)
SPHINCS+	𝑂(𝑛² log 𝑛)	𝑂(𝑛² log 𝑛)

• Kyber has significantly better performance than RSA due to its lattice-based optimizations (𝑂(𝑛 log 𝑛)).
• Dilithium is more efficient than RSA but slower than ECC.
• SPHINCS+ is slower than both due to its hash-tree structure.

---

4. Security Level Against Quantum Attacks

Let’s evaluate how traditional cryptographic security degrades under Shor’s Algorithm.

Algorithm	Security Against Classical Attacks (bits)	Security Against Quantum Attacks (bits)
RSA-2048	112	0 (Shor’s Algorithm Breaks It)
ECC P-256	128	0 (Shor’s Algorithm Breaks It)
Kyber-512	128	128
Kyber-768	192	192
Kyber-1024	256	256
Dilithium-2	128	128
SPHINCS+	128	128

• RSA and ECC drop to 0-bit security against quantum attacks making them completely insecure.
• Kyber, Dilithium and SPHINCS+ maintain their security levels as they are designed to resist quantum threats.
• SPHINCS+ uses hash-based cryptography which remains secure even against quantum attacks.

5. Computational Effort to Break Cryptographic Algorithms

Breaking encryption relies on the number of operations required to solve the underlying mathematical problems. Classical cryptography is based on integer factorization (RSA), discrete logarithms (ECC), and hash functions. Quantum computers particularly Shor’s algorithm significantly reduce the time required for factorization and logarithm-based schemes.

Classical vs. Quantum Attack Complexity

Algorithm	Security Basis	Classical Attack Complexity	Quantum Attack Complexity (Shor’s)
RSA-2048	Integer Factorization	( O(2^{112}) ) (General Number Field Sieve)	( O(n^3) ) (~8,000 Qubits needed)
ECC P-256	Discrete Logarithm	( O(2^{128}) ) (Pollard’s Rho)	( O(n^3) ) (~2,500 Qubits needed)
Kyber-512	Lattice-Based (LWE)	( O(2^{128}) )	( O(2^{128}) ) (Quantum advantage negligible)
Kyber-768	LWE	( O(2^{192}) )	( O(2^{192}) ) (Quantum advantage negligible)
Kyber-1024	LWE	( O(2^{256}) )	( O(2^{256}) ) (Quantum advantage negligible)
Dilithium-2	LWE	( O(2^{128}) )	( O(2^{128}) ) (Quantum advantage negligible)
SPHINCS+	Hash-Based (XMSS)	( O(2^{128}) )	( O(2^{128}) ) (Quantum advantage negligible)

• RSA-2048 and ECC P-256 are completely broken by Shor’s algorithm with a sufficiently powerful quantum computer.
• Kyber and Dilithium remain quantum-resistant because lattice-based problems are currently not known to be efficiently solvable by quantum algorithms.
• SPHINCS+ is based on hash functions, which remain resistant to quantum attacks but it has higher computational cost compared to lattice-based schemes.

6. Simulation of Computational Effort

To demonstrate how much effort it would take to break these cryptographic schemes let’s compare their estimated decryption times on different types of computing models.

Time to Break Encryption Using Supercomputers vs. Quantum Computers

Algorithm	Operations Required (Classical)	Time to Break on a Supercomputer (~10¹⁸ ops/sec)	Time to Break with a 1M Qubit Quantum Computer
RSA-2048	( 2^{112} ) (~5 × 10³³ ops)	~1 billion years	~10 seconds
ECC P-256	( 2^{128} ) (~3 × 10³⁸ ops)	~10 trillion years	~30 seconds
Kyber-512	( 2^{128} ) (~3 × 10³⁸ ops)	~10 trillion years	~10 trillion years (not broken)
Kyber-768	( 2^{192} ) (~6 × 10⁵⁷ ops)	~10²⁸ years	~10²⁸ years (not broken)
Kyber-1024	( 2^{256} ) (~1 × 10⁷⁷ ops)	~10⁴⁵ years	~10⁴⁵ years (not broken)
SPHINCS+	( 2^{128} ) (~3 × 10³⁸ ops)	~10 trillion years	~10 trillion years (not broken)

• Breaking RSA-2048 on a classical supercomputer takes about a billion years, while a 1M-qubit quantum computer can do it in seconds.
• ECC P-256 is similarly vulnerable.
• Kyber and Dilithium remain secure because their security relies on lattice-based problems, which remain resistant to quantum speedup.
• SPHINCS+ remains secure due to its hash-based structure, but its verification time is slower than lattice-based alternatives.

7. Energy Cost of Breaking Cryptography

Breaking cryptographic systems isn’t just about time it also requires vast amounts of energy.Let’s estimate the energy cost of breaking encryption using today’s most advanced supercomputers and potential future quantum computers.

Energy Consumption Estimates (in Megawatt-Hours)

Algorithm	Classical Computing Energy Cost (ExaFlop Supercomputer)	Quantum Computing Energy Cost (Assuming 1M-Qubit Machine)
RSA-2048	~500 Terawatt-hours (TWh)	~10 Megawatt-hours (MWh)
ECC P-256	~1,000 Terawatt-hours (TWh)	~50 Megawatt-hours (MWh)
Kyber-512	~1,000 Terawatt-hours (TWh)	~1,000 Terawatt-hours (TWh)
Kyber-768	~10⁵ TWh	~10⁵ TWh
Kyber-1024	~10⁷ TWh	~10⁷ TWh
SPHINCS+	~1,000 Terawatt-hours (TWh)	~1,000 Terawatt-hours (TWh)

• RSA and ECC are highly vulnerable because quantum computers require millions of times less energy to break them than classical supercomputers.
• Kyber, Dilithium, and SPHINCS+ remain impractical to break, even with quantum speedups, because their security levels remain high.

---

8. Summary of Computational and Energy Effort

Algorithm	Classical Security	Quantum Security	Time to Break (Quantum)	Energy to Break (Quantum)
RSA-2048	112-bit	0-bit (Broken)	~10 seconds	~10 MWh
ECC P-256	128-bit	0-bit (Broken)	~30 seconds	~50 MWh
Kyber-512	128-bit	128-bit	10 trillion years	~10⁵ TWh
Kyber-768	192-bit	192-bit	10²⁸ years	~10⁷ TWh
Kyber-1024	256-bit	256-bit	10⁴⁵ years	~10¹⁰ TWh
SPHINCS+	128-bit	128-bit	10 trillion years	~10⁵ TWh

Final Takeaways

• Quantum computers completely break RSA and ECC encryption within seconds.
• Kyber, Dilithium, and SPHINCS+ remain highly secure, even against quantum attacks.
• The computational cost and energy needed to break post-quantum cryptography (PQC) make them infeasible to attack, ensuring long-term security.
• This analysis highlights why governments and enterprises are transitioning to PQC to secure data against future threats.

---

Conclusion

The dawn of quantum computing casts a long shadow over our current cryptographic infrastructure. As we’ve explored traditional algorithms like RSA and ECC cornerstones of modern security face imminent vulnerability. The NIST’s selection of CRYSTALS-Kyber CRYSTALS-Dilithium and SPHINCS+ marks a pivotal shift towards quantum-resistant solutions paving the way for a secure digital future.

These new algorithms while offering robust protection against quantum threats present their own set of challenges. Larger key and signature sizes and varying computational costs require careful consideration and optimization. The transition to PQC is not merely a matter of swapping algorithms.It necessitates a comprehensive overhaul of existing systems, protocols and standards.

Citations

https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards

https://csrc.nist.gov/News/2024/postquantum-cryptography-fips-approved

https://en.wikipedia.org/wiki/Post-quantum_cryptography

https://pq-crystals.org/kyber/

https://pq-crystals.org/dilithium/

https://sphincs.org/

https://www.redhat.com/en/blog/post-quantum-cryptography-lattice-based-cryptography

https://www.redhat.com/en/blog/post-quantum-cryptography-hash-based-signatures

https://www.redhat.com/en/blog/post-quantum-cryptography-code-based-cryptography

Some of the Mathematical computation examples in this blog post are written with the help of AI.

Image Courtesy : Generated using AI (Adobe Firefly)