Skip to content

Cryptography Overview

Two Main Types

  • Symmetric encryption
  • Same key for encryption and decryption.
  • Asymmetric encryption
  • Different keys: public key (encrypt) and private key (decrypt).

AES (Symmetric)

  • Alice and Bob share a secret password $ P $.
  • Encryption:
    $$ E = \text{enc}(msg, P) $$
  • Transmission:
    $$ A \longrightarrow B $$
  • Decryption:
    $$ M = \text{dec}(E, P)=msg $$

RSA (Asymmetric) – Simplified

  • Public key: $ N $ (everybody knows it)
  • Private key: $ (a, b) $ such that $ a \cdot b = N $

Protocol: - Alice computes and sends: $$ E = \text{enc}(msg, N) \quad \text{(using public key $ N $)} $$ - Bob decrypts:
$$ M = \text{dec}(E, (a, b)) = msg $$

Note: In real RSA, the public key is \((N, e)\) and private key is \(d\) with \(ed \equiv 1 \pmod{\phi(N)}\). The factorization of \(N = p \cdot q\) is kept secret.

Quantum Speedups

Symmetric Cryptography

  • Suppose there are $ n $ possible keys.
  • Classical brute‑force: $ O(n) $ tests.
  • Quantum: $ O(\sqrt{n}) $ using Grover's Algorithm.

Asymmetric Cryptography

  • Let $ N $ be an $ n $-bit integer.
  • Classical: best known factoring algorithms run in sub‑exponential time (no proof that polynomial time is impossible).
  • Quantum: $ O(n^3) $ using Shor's Algorithm.

Shor's Algorithm – Factoring Integers

Goal: Factor $ N $ into two non‑trivial factors $ x, y $ (i.e., $ x \cdot y = N $ and $ x, y \neq 1 $).

Step 1 – Handle Easy Cases

If $ N $ is a prime power, it can be factored easily by classical methods.

Pick a random integer $ a $ with $ 2 \leq a \leq N-1 $.

Compute $ \gcd(a, N) $.

  • If $ \gcd(a, N) \neq 1 $, we have already found a factor of $ N $.

Step 2 – Find the Order \(r\)

If $ \gcd(a, N) = 1 $ (i.e., $ a $ is coprime to $ N $), then there exists an integer $ r > 0 $ such that
$$ a^r \equiv 1 \pmod{N} $$ $ r $ is called the order of $ a $ modulo $ N $.

Because $ a^{s+r} \equiv a^s \pmod{N} $, the function $ f(x) = a^x \bmod N $ is periodic with period $ r $.

Step 3 – Quantum Part: Finding $ r $

Classical: try one value of $ r $ at a time → slow.

Quantum:

  • Prepare superposition over all $ x $:
    $$ |x\rangle \otimes |0\dots 0\rangle \;\longrightarrow\; |x\rangle \otimes |a^x \bmod N\rangle $$
  • The second register (ancilla) holds the value $ a^x \bmod N $.
  • After measurement, the state collapses to a superposition of all $ x $ that give the same residue modulo $ r $.
  • Apply the Quantum Fourier Transform (QFT) to extract the period $ r $.

Step 4 – Using $ r $ to Factor $ N $

If $ r $ is odd, go back to Step 1 and pick a new $ a $.

If $ r $ is even, then
$$ (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod{N} $$ - Compute $ x = a^{r/2} \bmod N $, $ y = a^{r/2} \bmod N $ (actually we consider the two factors). - Compute $ \gcd(a^{r/2} - 1, N) $ and $ \gcd(a^{r/2} + 1, N) \(. - With high probability (\)\geq \frac{3}{8}$), one of these gcds yields a non‑trivial factor of $ N $.

Grover's Algorithm – Unstructured Search

Setting

  • We have a function $ f(x) $ that returns 1 for the correct input (the "marked" item) and 0 otherwise.
  • Goal: find the marked item among $ N = 2^n $ possibilities.

Oracle and Diffusion Operator

  • Oracle $ U_f $: $$ U_f |x\rangle = \begin{cases} -|x\rangle & \text{if } x \text{ is correct}\ |x\rangle & \text{if } x \text{ is incorrect} \end{cases} $$ This flips the amplitude sign of the correct state.

  • Diffusion operator $ D $: Reflects every amplitude about the mean amplitude. $$ D = 2|\psi\rangle\langle\psi| - I $$ where $ |\psi\rangle $ is the equal superposition state.

Amplitude Amplification Process

  • Start with equal superposition: each amplitude $ = \frac{1}{\sqrt{N}} $.
  • If the correct state is $ |1001\rangle $, its amplitude initially is $ \frac{1}{\sqrt{N}} $.
  • Apply $ U_f $ (flip sign of correct state), then apply $ D $ (reflect about mean).
  • After one Grover iteration, amplitude of the correct state grows while others shrink.

Iteration Count

  • Let $ C = \sqrt{N} $. The amplitude after $ x $ iterations satisfies: $$ |b_x| = \left| \sin\big((2x+1)\arcsin(1/\sqrt{N})\big) \right| $$
  • To obtain probability close to 1, we need about
    $$ x \approx \frac{\pi}{4}\sqrt{N} $$ iterations.

Complexity

  • Query complexity: $ O(\sqrt{N}) $.
  • Total runtime: $ O(\sqrt{N} \cdot (\log N)^2) $ (including gate overhead).
  • Space requirement: $ O(\log N) $ qubits.

Summary Table

Algorithm Problem Classical Complexity Quantum Complexity
Grover Unstructured search $ O(N) $ $ O(\sqrt{N}) $
Shor Integer factorization sub‑exponential $ O(n^3) $

\(N\): size of search space (for Grover) or the integer to factor (for Shor); \(n\): number of bits.