Post Quantum Crypto

How to read this page: This article maps the topic from beginner to expert across six levels � Remembering, Understanding, Applying, Analyzing, Evaluating, and Creating. Scan the headings to see the full scope, then read from wherever your knowledge starts to feel uncertain. Learn more about how BloomWiki works ?

Post-Quantum Cryptography (PQC) is the development of cryptographic algorithms that are thought to be secure against an attack by a quantum computer. While current supercomputers would take trillions of years to break our most common encryption (like RSA and ECC), a future "Large-Scale Quantum Computer" could do it in minutes using Shor's Algorithm. PQC is the "Race against the Clock" to replace the math of the internet before these powerful machines are built. It involves finding new, "Quantum-Hard" mathematical puzzles—like the math of lattices, codes, and multivariate equations—that even a computer using the laws of quantum physics cannot solve.

Remembering

• Post-Quantum Cryptography (PQC) — Cryptographic algorithms (usually public-key) that are secure against both quantum and classical computers.
• Quantum Computer — A computer that uses quantum-mechanical phenomena (like superposition) to perform calculations much faster than traditional computers for certain tasks.
• Qubit — The basic unit of quantum information (unlike a 0 or 1 bit, it can be both at once).
• Shor's Algorithm — A quantum algorithm that can find the prime factors of a large number instantly (breaking RSA).
• Grover's Algorithm — A quantum algorithm that can speed up "searching" a list, making symmetric keys (like AES) 2x weaker.
• Lattice-Based Cryptography — PQC based on the difficulty of finding the "shortest path" in a multi-dimensional grid of points.
• NIST PQC Competition — The global effort by the US government to select and standardize the next generation of encryption.
• Kyber / Dilithium — The names of two of the primary PQC algorithms selected for standardization.
• Cryptographic Agility — The ability of a system to easily "swap out" an old encryption method for a new one without breaking.
• Harvest Now, Decrypt Later — The strategy used by spies to steal encrypted data *today* in the hope that they can decrypt it with a quantum computer in 10 years.
• Hash-Based Signatures — Digital signatures based on hash functions, which are naturally very resistant to quantum attacks.
• Isogeny-Based Cryptography — PQC based on the mathematical maps between different elliptic curves.

Understanding

PQC is understood through the Quantum Threat and Mathematical Hardness.

1. The "Quantum Apocalypse" (Y2Q): Most of the internet's trust is built on one simple math problem: "It is hard to factor two big prime numbers."

• Quantum computers use Superposition to check millions of "paths" to the factors at once.
• This isn't just a "faster computer," it's a New Physics.
• If a quantum computer is built before we switch to PQC, every bank account, every secret message, and every digital signature on Earth becomes vulnerable.

2. Finding 'Quantum-Hard' Problems: PQC researchers look for math that even a quantum computer finds hard.

• Lattices: Imagine a grid of points in 500 dimensions. If I give you a random spot in space, can you find the *closest* grid point? Even with quantum tricks, this is an "unsolvable" task in a reasonable amount of time.
• Code-Based: Based on the math of correcting errors in data transmissions (Error Correcting Codes).

3. Symmetric vs. Asymmetric:

• Asymmetric (Public Key): Is Dead when quantum arrives. RSA and ECC must be replaced entirely by PQC.
• Symmetric (AES): Is Safe but "Weakened." A 128-bit key becomes as easy to break as a 64-bit key. To stay safe, we just need to double the key size to 256 bits.

Cryptographic Agility: This is the most important lesson of PQC. We used to think encryption was "forever." PQC teaches us that we must build our software so that we can change the "Math" in 24 hours if a new threat is discovered.

Applying

Modeling 'The Quantum Advantage' (Classical vs. Quantum): <syntaxhighlight lang="python"> def estimate_crack_time(key_bits, is_quantum):

   """
   Shows why RSA dies and AES survives.
   """
   if is_quantum:
       # Shor's Algorithm 'flattens' the difficulty of RSA
       crack_time = "Seconds"
   else:
       # Standard computer guessing
       combinations = 2 ** key_bits
       crack_time = f"{combinations} operations (Trillions of years)"
       
   return crack_time

1. RSA-2048 (The current standard)

print(f"RSA vs Classical: {estimate_crack_time(2048, False)}") print(f"RSA vs Quantum: {estimate_crack_time(2048, True)}")

1. This is why the world is currently moving to 'Lattice'
2. math for the next generation of HTTPS.

</syntaxhighlight>

PQC Landmarks

Peter Shor (1994) → The mathematician who proved that quantum computers *could* break our math, starting the PQC field.

NIST Standard (2022) → The announcement of the first 4 "Winners" of the global PQC competition.

Quantum Key Distribution (QKD) → A different approach using lasers to send keys; if anyone "looks" at the key, the quantum state collapses and the intrusion is detected.

Hybrid PQC → Using *both* RSA and a PQC algorithm together; if the new PQC math is found to have a bug, the old RSA math still protects you from classical hackers.

Analyzing

RSA vs. Lattice-Based (PQC)

Feature	RSA (Current)	ML-KEM (Kyber - PQC)
Math Basis	Prime Factorization	Learning With Errors (Lattices)
Key Size	Large (2048 bits)	Smaller / Medium
Speed	Fast enough	Very Fast
Quantum Safe?	NO	YES
Main Use	Web Security (HTTPS)	The Future of Web Security

The Concept of "Mosca's Theorem": This is a formula for the "Panic Level": $X + Y > Z$.

• X: How long it takes to build a new infrastructure (e.g., 10 years).
• Y: How long the data must stay secret (e.g., 20 years for a government).
• Z: How long until a large quantum computer is built (e.g., 15 years).

If $X + Y$ is larger than $Z$, then you have already failed. We need to start PQC Now to protect data that needs to stay secret until 2045.

Evaluating

Evaluating a PQC algorithm: (1) Mathematical Confidence: How many geniuses have tried and failed to break the math? (2) Performance: Do the keys take up too much space (some PQC keys are huge)? (3) Implementation Security: Is the code "easy to write wrong" in a way that creates a leak? (4) Side-Channel Resistance: Is the algorithm safe from a spy measuring the computer's power or heat?

Creating

Future Frontiers: (1) Fully Homomorphic Encryption (FHE): Using PQC math to build a world where "Data Privacy" is a law of math, not just a promise from a company. (2) Quantum-Resistant Blockchain: Updating the signatures in Bitcoin and Ethereum so your money can't be stolen by a quantum hacker. (3) Post-Quantum VPNs: Protecting the "Tunnels" of the internet today so they can't be decrypted in 20 years. (4) Universal Cryptography: The dream of a single math system that works for encryption, signatures, and computation, and is safe from every possible computer.