ISE Cryptography — Reference

Quantum Algorithms for Cryptography

Quantum Computing in 5 Minutes

Just enough to understand Grover and Shor.

Classical Bits vs Qubits

A classical bit is 0 or 1. That’s it. Pick one.
A qubit can be in a superposition of both 0 and 1 simultaneously
- Analogy: a coin on a table is heads or tails. A spinning coin is “both” until it lands.
When you measure a qubit, it collapses to 0 or 1 (the coin lands)
- The probabilities of each outcome are controlled by amplitudes
- An amplitude is a number whose square gives the probability
- For a fair superposition: amplitude \(1/\sqrt{2}\) for each, probability \(1/2\) each
The qubit is not “secretly” 0 or 1 before measurement
- It genuinely exists in both states at once. This is quantum mechanics, not randomness.

Superposition and Parallelism

With \(n\) qubits in superposition, you represent \(2^n\) states simultaneously
- 10 qubits: 1024 states. 265 qubits: more states than atoms in the observable universe.
A quantum operation (gate) acts on all \(2^n\) states at once
- This is quantum parallelism: one operation, \(2^n\) inputs processed
The catch: you can only read one outcome when you measure
- All that parallelism collapses to a single answer
The trick: use interference to make the right answer more probable and wrong answers less probable
- This is what makes quantum algorithms hard to design and powerful when they work

Interference: The Quantum Trick

Amplitudes can be positive or negative (unlike probabilities, which are always positive)
When two paths to the same outcome have opposite-sign amplitudes, they cancel out (destructive interference)
When two paths have the same sign, they reinforce (constructive interference)
Quantum algorithms are about engineering interference patterns:
- Wrong answers: paths cancel, probability drops toward 0
- Right answer: paths reinforce, probability rises toward 1
Classical analogy: noise-cancelling headphones use destructive interference to remove unwanted sound

Reading Quantum Notation

Quantum computing uses Dirac notation (also called bra-ket notation)
The symbol \(|x\rangle\) is called a ket (read aloud: “ket x” or “ket zero” for \(|0\rangle\))
- The \(|\) and \(\rangle\) are just brackets, like parentheses. The label inside names the state.
- \(|0\rangle\): “ket zero”, the qubit in state 0
- \(|1\rangle\): “ket one”, the qubit in state 1
- \(|\text{correct}\rangle\): “ket correct”, whatever state we’ve labelled “correct”
A superposition is a weighted sum of kets:
- \(|+\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\), read “ket plus equals one-over-root-two ket zero plus one-over-root-two ket one”
- The \(1/\sqrt{2}\) factors are the amplitudes. Square to get probability: \((1/\sqrt{2})^2 = 1/2\)

Dirac Notation: Quick Reference

Notation	Read aloud	Meaning
\(\lvert 0 \rangle\)	“ket zero”	Qubit in state 0
\(\lvert 1 \rangle\)	“ket one”	Qubit in state 1
\(\lvert + \rangle\)	“ket plus”	Equal superposition of 0 and 1
\(\lvert - \rangle\)	“ket minus”	Equal superposition with a phase flip
\(\lvert 01 \rangle\)	“ket zero-one”	Two qubits: first is 0, second is 1
\(\lvert \psi \rangle\)	“ket psi”	An arbitrary quantum state

We use this notation throughout the rest of this deck
- Wherever you see \(|\text{something}\rangle\), it’s just a label for a quantum state
- The maths around it (addition, coefficients) describes superpositions

Quantum Circuits

A quantum algorithm is a sequence of gates applied to qubits, drawn as a circuit:
- H (Hadamard) gate: puts a qubit into equal superposition (\(|0\rangle \to |+\rangle\))
- CNOT gate: flips the target qubit if the control qubit is \(|1\rangle\)
- Together, H + CNOT can create entanglement (correlations between qubits that have no classical analogue)
A quantum algorithm is just a sequence of these gates, then a measurement at the end
- Like a classical program is a sequence of instructions
- The art is choosing gates so that interference amplifies the correct answer

Oracles

An oracle is a black-box function you can query: “is this the item I’m looking for?”
- In Grover’s algorithm: the oracle checks “is this the correct key?”
- It flips the sign of the amplitude for the correct item (marks it)
You don’t need to know how the oracle is built internally
- Classically, checking one key takes one AES evaluation
- Quantumly, the oracle evaluates AES on all \(2^{128}\) keys simultaneously in one call
- This isn’t magic: the oracle is a quantum circuit that computes AES reversibly, and quantum parallelism does the rest
“But surely building the oracle takes ages?” Building the circuit takes effort (proportional to the cost of one AES evaluation), but once built, each call processes all keys at once
The oracle is the interface between the quantum algorithm and the real-world problem

Grover’s Algorithm

Finding a needle in a haystack, quantumly.

The Search Problem

You have \(N\) items. Exactly one is “marked” (the correct key). Find it.
Classically: check one at a time. On average, \(N/2\) checks. No way around it.
Quantumly: Grover’s algorithm finds the marked item in \(\approx \sqrt{N}\) checks
- For AES-128: \(N = 2^{128}\), so \(\sqrt{N} = 2^{64}\). A quadratic speedup.
How? Not by checking faster. By checking smarter, using interference.

Grover’s Idea: Amplitude Amplification

Step 0: put all \(N\) items in equal superposition
- Each item has amplitude \(1/\sqrt{N}\), probability \(1/N\)
- “Wait, doesn’t creating \(N\) states take \(N\) steps?” No! Apply an H gate to each of \(n\) qubits (\(N = 2^n\)). That’s \(n\) operations, not \(N\). For AES-128: just 128 gates to create \(2^{128}\) states.
Step 1 (Oracle): flip the sign of the marked item’s amplitude
- It goes from \(+1/\sqrt{N}\) to \(-1/\sqrt{N}\)
- Every other item stays at \(+1/\sqrt{N}\)
- The oracle runs on the entire superposition in one call. It doesn’t check items one at a time.
Step 2 (Diffusion): reflect all amplitudes about the average
- The average is now slightly below \(1/\sqrt{N}\) (because one item is negative)
- Items above average get pushed down, items below average get pushed up
- The marked item (far below average, negative) gets a big boost
Repeat Steps 1-2. Each iteration, the marked item’s amplitude grows.

The Geometry: Rotation on a Circle

The state of the system lives in a 2D plane:
- One axis: \(|\text{correct}\rangle\) (the marked item)
- Other axis: \(|\text{wrong}\rangle\) (everything else)

Each Grover iteration rotates the state by \(2\theta\) toward \(|\text{correct}\rangle\)
After \(\approx \sqrt{N}\) rotations, the state is aligned with \(|\text{correct}\rangle\)

Why Exactly \(\sqrt{N}\)?

The initial angle \(\theta \approx 1/\sqrt{N}\) (for large \(N\), the state is almost entirely \(|\text{wrong}\rangle\))
Each iteration rotates by \(2\theta \approx 2/\sqrt{N}\) radians
To rotate from \(\theta\) to \(\pi/2\) (fully aligned with \(|\text{correct}\rangle\)):
- Number of iterations \(\approx \frac{\pi/2}{2/\sqrt{N}} = \frac{\pi \sqrt{N}}{4} \approx \sqrt{N}\)
Important: more iterations overshoot!
- The state rotates past \(|\text{correct}\rangle\) and the probability drops
- You have to stop at the right time
The \(\sqrt{N}\) is not a design choice. It’s a geometric consequence of the rotation angle.

Grover’s Applied to AES

The oracle: given a known plaintext-ciphertext pair \((m, c)\), check if \(E(k, m) = c\)
For AES-128: \(N = 2^{128}\) possible keys
- Classical exhaustive search: \(2^{128}\) evaluations
- Grover’s: \(\sqrt{2^{128}} = 2^{64}\) evaluations
For AES-256: \(N = 2^{256}\) possible keys
- Grover’s: \(\sqrt{2^{256}} = 2^{128}\) evaluations
- That’s still 128-bit security. Safe.
The fix for symmetric crypto is simple: double the key size
- AES-256 and ChaCha20 (256-bit keys) are already quantum-safe

Grover’s Limitations

Grover’s gives a quadratic speedup, not exponential
- \(\sqrt{N}\) vs \(N\), not \(\log N\) vs \(N\)
- This is a fundamental limit proved by Bennett et al. (1997): no quantum algorithm can search faster than \(\sqrt{N}\)
Only works for unstructured search (no exploitable structure)
- If the problem has structure (like factoring), specialised algorithms (like Shor’s) can do much better
Current quantum hardware: \(\approx\) 1,000-1,200 noisy physical qubits on leading systems (IBM Condor, Atom Computing, Google Willow)
- AES-128 would need a few thousand error-corrected logical qubits, which translates to millions of physical qubits after error-correction overhead
- We’re decades away from this being a practical threat
Bottom line: Grover’s is a threat to plan for (use AES-256), not a threat to panic about today

Shor’s Algorithm

The one that breaks public-key cryptography.

The Problem Shor Solves

Given \(N = p \times q\) (product of two large primes), find \(p\) and \(q\)
- This is the integer factorisation problem. RSA depends on this being hard.
Also: given \(g\) and \(g^\alpha \bmod p\), find \(\alpha\)
- This is the discrete logarithm problem. DH and ECDH depend on this being hard.
Classically: best factoring algorithm (number field sieve) is sub-exponential
- Hard enough for 2048-bit RSA to be safe (for now)
Shor’s algorithm (1994): solves both problems in polynomial time on a quantum computer
- This is an exponential speedup, not just quadratic like Grover’s

Factoring = Period Finding

The key insight is entirely classical (no quantum needed!):
- Pick a random \(a < N\)
- The sequence \(a^1 \bmod N,\; a^2 \bmod N,\; a^3 \bmod N,\; \ldots\) is periodic
- It repeats with some period \(r\): \(a^r \equiv 1 \pmod{N}\)
If \(r\) is even and \(a^{r/2} \not\equiv -1 \pmod{N}\):
- Then \(\gcd(a^{r/2} - 1,\; N)\) gives a non-trivial factor of \(N\)
- (This works because \(a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod{N}\))
The hard part: finding the period \(r\)
- Classically, you’d need up to \(r\) modular multiplications to detect the cycle, and \(r\) can be as large as \(N\) itself, so the cost is exponential in \(\log N\)
- Quantumly, this is where the magic happens

Quantum Period Finding

Create a superposition of all exponents: \(\sum_{x=0}^{Q-1} |x\rangle\,|a^x \bmod N\rangle\)
- The second register now has a periodic structure (period \(r\))
Apply the Quantum Fourier Transform (QFT) to the first register
- The QFT converts periodic time-domain data into frequency-domain peaks
- Like the classical FFT, but on quantum amplitudes
Measuring the first register gives a value close to a multiple of \(Q/r\)
- From a few measurements, extract \(r\) using continued fractions (classical math)
The QFT runs in \(O(n^2)\) gates on \(n\) qubits
- This is exponentially faster than classical period-finding on \(2^n\) values
- This is where the exponential speedup comes from

The Quantum Fourier Transform (Intuition)

Classical analogy: tuning a guitar with a tuner
- The tuner “hears” a vibrating string (periodic signal) and finds its frequency
- The FFT does this mathematically: periodic input \(\to\) sharp frequency peak
The QFT does the same thing, but on quantum amplitudes instead of sound waves
- A state with period \(r\) produces a sharp peak at frequency \(1/r\) after QFT
- Interference amplifies the peak (constructive) and suppresses noise (destructive)
Why it’s fast:
- Classical FFT on \(2^n\) data points: \(O(n \cdot 2^n)\) operations
- Quantum QFT on \(n\) qubits (representing \(2^n\) amplitudes): \(O(n^2)\) gates
- The exponential data is “already there” in superposition; the QFT just transforms it

Shor’s Algorithm: Putting It Together

Step 1: pick random \(a\), compute \(\gcd(a, N)\). If \(> 1\), you got lucky (done)
Step 2: use quantum period-finding to get \(r\) (the order of \(a \bmod N\))
Step 3: if \(r\) is even and \(a^{r/2} \not\equiv -1 \pmod{N}\), compute \(\gcd(a^{r/2} - 1, N)\)
Step 4: this gives a non-trivial factor of \(N\). Repeat with new random \(a\) if needed.
Total complexity: polynomial in \(\log N\) (the number of digits of \(N\))
- Compare classical NFS: sub-exponential in \(\log N\)
- For RSA-2048: Shor’s would take hours on a quantum computer; NFS would take longer than the age of the universe

Shor’s Applied to RSA and DH

RSA-2048: Shor’s needs \(\approx\) 4,000 logical qubits
- Each logical qubit needs \(\approx\) 5,000 physical qubits for surface-code error correction
- Total: \(\approx\) 20 million physical qubits (Gidney & Ekerå, 2021)
- Current state of the art: \(\approx\) 1,000 noisy physical qubits. Still a big gap.
Discrete log (DH, ECDH): Shor’s solves this too via period-finding in \(\mathbb{Z}_p^*\)
- ECDLP needs fewer qubits than RSA factoring, but still millions
Timeline estimates for “cryptographically relevant quantum computers” vary widely:
- Optimistic: 2030s. Conservative: 2040s+. Unknown unknowns: engineering breakthroughs could accelerate.
The honest answer: nobody knows when, but the direction is clear

Why Shor’s is Different from Grover’s

Grover’s: quadratic speedup (\(\sqrt{N}\) vs \(N\))
- Affects: symmetric crypto (AES, ChaCha20)
- Fix: double the key size (AES-256). Simple.
Shor’s: exponential speedup (polynomial vs sub-exponential)
- Affects: asymmetric crypto (RSA, DH, ECDH, ECDSA)
- Fix: change the math entirely. Bigger keys won’t help.
This asymmetry is why post-quantum cryptography exists:
- It replaces RSA/DH/ECDH with new hard problems (lattices, codes, hashes)
- These problems are believed to be hard even for quantum computers
- NIST standardised: ML-KEM (FIPS 203), ML-DSA (FIPS 204), SLH-DSA (FIPS 205)

What This Means for Cryptography

Connecting the algorithms to the real world.

The Quantum Threat Landscape

Primitive	Classical security	Quantum threat	Mitigation
AES-128	128-bit	64-bit (Grover)	Use AES-256
AES-256	256-bit	128-bit (Grover)	Already safe
ChaCha20	256-bit	128-bit (Grover)	Already safe
RSA-2048	\(\approx\) 112-bit	0-bit (Shor)	ML-KEM (FIPS 203)
ECDH (P-256)	128-bit	0-bit (Shor)	ML-KEM (FIPS 203)
ECDSA (P-256)	128-bit	0-bit (Shor)	ML-DSA (FIPS 204)

Symmetric crypto: wounded but survivable (double the key)
Asymmetric crypto: completely broken (must replace the math)

Harvest Now, Decrypt Later

Adversaries don’t need a quantum computer today to benefit from one tomorrow
Harvest now, decrypt later: record encrypted traffic now, store it, decrypt later when quantum hardware matures
Data with long-term value is at risk today:
- Medical records (decades of relevance)
- State secrets and intelligence (decades of classification)
- Financial data (years of regulatory retention)
- Personal communications (privacy is forever)
This is why the migration to post-quantum crypto is urgent
- Not because quantum computers exist, but because encrypted data is being stored now

The Migration Path

Symmetric crypto: already safe with AES-256 and ChaCha20. No changes needed.
Asymmetric crypto: replace RSA/DH/ECDH with lattice-based schemes
- ML-KEM (FIPS 203): post-quantum key encapsulation
- ML-DSA (FIPS 204): post-quantum digital signatures
- SLH-DSA (FIPS 205): hash-based signatures (stateless, conservative fallback)
Transition strategy: hybrid schemes use both classical AND post-quantum
- Example: X25519MLKEM768 combines X25519 (classical ECDH) with ML-KEM-768 (post-quantum)
- If either holds, the scheme is secure. Belt and braces.
Already deployed in production:
- TLS 1.3: Chrome and Firefox use X25519MLKEM768 by default (previously X25519Kyber768; Kyber was renamed to ML-KEM in FIPS 203)
- Signal: PQXDH protocol with Kyber-1024
- iMessage: PQ3 with Kyber-768

Notation Summary

Concept	Meaning	Used in
Grover’s algorithm	Quantum search: \(O(\sqrt{N})\)	Block Ciphers (AES security)
Shor’s algorithm	Quantum period-finding: polynomial time	Public Key Crypto (RSA/DH/ECDH)
Amplitude amplification	Boost correct answer via interference	Grover’s algorithm
QFT	Quantum Fourier Transform: finds periods	Shor’s algorithm
Harvest now, decrypt later	Record today, decrypt with future QC	All asymmetric crypto
ML-KEM (FIPS 203)	Post-quantum key encapsulation (lattice-based)	Replacing RSA/ECDH
ML-DSA (FIPS 204)	Post-quantum signatures (lattice-based)	Replacing ECDSA
SLH-DSA (FIPS 205)	Post-quantum signatures (hash-based)	Conservative fallback