How quantum algorithms are fundamentally different and what does it mean for cryptographic security schemes

2025-05-19 crypto programming sketch

TL;DR

What's Safe:

AES-256
SHA-512
Lattice-based encryption (e.g. Kyber, Homomorphic Encryption)
Hash-based signatures (e.g. XMSS)

What's Broken:

RSA
ECC (including Bitcoin-style signatures)
Diffie-Hellman key exchange

3Blue1Brown > But what is Quantum Computing?

Quantum computers aren’t just faster, but fundamentally more powerful. Because they tap into computational resources classical systems don’t have access to — not just clock cycles, but dimensions of parallelism embedded in the laws of quantum mechanics.

They exploit quantum mechanical principles that do not exist in classical computing. These principles allow quantum algorithms to process information in ways that classical algorithms cannot, often yielding exponential or quadratic speedups for certain problems.

This makes certain intractable problems — such as breaking RSA or searching unstructured databases efficiently solvable.

Key features making quantum algorithms fundamentally different

1. Superposition

Classical bit ∈ {0, 1}
Quantum bit (qubit) ∈ linear combination of both states: α|0⟩ + β|1⟩
A register of n qubits encodes 2ⁿ basis states simultaneously

This allows quantum computers to explore many possible inputs at once.

Implication: A quantum computer with \(n\) qubits can represent \(2^n\) states at once — enabling parallel computation on an exponential scale (in theory).

2. Entanglement

Classically, variables are independent unless explicitly correlated.
Qubits can be entangled: observing one instantly determines the other.

Implication: Allows non-local correlations used to coordinate qubit behavior across a quantum system. Entanglement is not just a novelty — it’s required for many quantum speedups.

3. Interference

Quantum amplitudes interfere: they can add or cancel out.
Algorithms are constructed so that correct solutions interfere constructively and incorrect ones destructively.

Implication: Quantum computation isn’t just parallel brute-force. It’s carefully engineered amplitude shaping to converge toward the correct output with high probability.

4. Measurement Collapse

Once you measure a quantum state, it collapses to a definite classical value.
Quantum algorithms are designed so that, by the end of computation, the desired result has high probability upon measurement.

Effect: This constraint forces clever design: you can only extract limited information from a quantum state, so algorithms must concentrate the right answer before measurement.

Canonical Quantum Algorithms (and What They Break)

Algorithm	Problem Solved	Classical Cost	Quantum Cost	Consequence
Shor's	Integer factoring, discrete logs	Exponential	Polynomial	Breaks RSA, DSA, ECC
Grover's	Unstructured search	O(N)	O(√N)	Halves effective key sizes
Quantum Phase Estimation	Eigenvalue estimation	—	—	Core primitive in Shor’s, chemistry, etc.
Quantum Fourier Transform	Period finding, hidden subgroup	Exponential	Polynomial	Key subroutine in Shor’s

Summary of Fundamental Differences

Feature	Classical Algorithms	Quantum Algorithms
Information Unit	Bit (0 or 1)	Qubit (superposition of 0 and 1)
Parallelism	Deterministic or randomized	Massive parallelism via superposition
Correlation	Probabilistic independence	Entanglement with non-classical links
Information Flow	Linear, branching	Interference-based computation
Output	Deterministic or probabilistic	Probabilistic, must extract via measurement

Security schemes: post-quantum vs pre-quantum

A security scheme (such as an encryption algorithm or digital signature scheme) is considered post-quantum if it is believed to be secure against attacks using quantum computers. This determination involves a combination of theoretical analysis, cryptanalysis, and community consensus.

Resistance to known quantum algorithms

The post-quantum schemes must resist known quantum attacks, primarily:

Shor’s Algorithm: Breaks widely used public-key schemes like RSA, DSA, and ECC by factoring integers and computing discrete logarithms efficiently on a quantum computer.
Grover’s Algorithm: Speeds up brute-force attacks against symmetric-key algorithms, cutting the effective key size in half.

Post-quantum cryptographic schemes are based on mathematical problems that are (as far as currently known) not efficiently solvable by quantum algorithms, such as:

Lattice-based problems (e.g., learning with errors (LWE).md)
Code-based problems (e.g., McEliece cryptosystem)
Multivariate polynomial problems
Hash-based constructions
Isogeny-based problems (though some recent proposals like SIKE were broken)

Security level classification

Symmetric algorithms like AES-256 are considered post-quantum secure (due to Grover’s algorithm, 256-bit AES offers ~128-bit quantum security).
RSA-3072 or ECC P-256 are not post-quantum secure due to vulnerability to Shor’s algorithm.

Incoming Internal References (0)

Outgoing Internal References (11)

Outgoing Web References (1)

ubstack.com/home/post/p-162532597
- But what is Quantum Computing?