Simon's Period

Simon's algorithm · hidden period · quantum symmetric attacks

Press measure and watch half of every possible answer cancel itself out — then watch the surviving equations pin down a block cipher's key in a handful of queries instead of millions.

Break Even-Mansour ↓

Some functions repeat. Feed one a value, feed it a second value, and you get the same answer back — and the gap between those two inputs is always the same secret gap, everywhere in the function. That gap is called the period. An ordinary computer can only find it by hunting for a repeat, which takes roughly the square root of the number of inputs: get to a few hundred bits and it is hopeless.

A quantum computer can ask about every input at once, and then — this is the part with no classical counterpart — arrange for all the wrong answers to destroy each other before you look. What survives is always a clue about the period, and a handful of clues is enough. Not a faster search. A different shape of question. Below, you get to ask it.

Run Simon's algorithm

Pick a target. Each press of Measure runs one complete round of the circuit — one superposition query to the function, one interference step, one measurement — and hands you a single linear equation about the hidden period. Collect enough independent equations and the period is forced. Nothing is searched, nothing is guessed — the candidate falls out of the equations, and is then checked against f before anything is claimed.

Target function

Input width n

The whole domain is 2ⁿ inputs. The algorithm's query count grows linearly with n; it is this classical simulator whose memory and runtime double with every extra bit.

—

input: —
output: —

The circuit, one round

One press = one query to f. Watch the query counter, not the clock.

Independent equations 0 / 0

The period is pinned once the rank reaches n−1 — one dimension short of everything.

oracle queries: 0
equations that taught nothing: 0
periods still possible: —

Verdict

Not started

Press Measure once to send the first query.

IF THE PERIOD FALLS

—

Why at least half the answers vanish

This is the whole trick, and it has no classical analogue. After the query, the machine holds every input that shares the observed output — for a function satisfying Simon's promise exactly that is a pair, x₀ and x₀ ⊕ s; a construction that collides by accident on top of its period can leave a larger class, and an injective f leaves a single input and no interference at all. The final Hadamard sends each surviving input down a path to every possible outcome y, with a sign of + or −. Where the signs disagree, the paths cancel and that outcome becomes impossible. Every y with y · s = 1 cancels, which is half of them; a larger preimage class can cancel more.

Before the final Hadamard

Run a measurement to populate this.

After the final Hadamard

Cells reading 0 were cancelled by interference.

amplitude positive amplitude negative cancelled — impossible outcome the outcome measured

Do the arithmetic yourself

Select an outcome in the after grid and every path contributing to it is computed here, independently, and added — two for a clean pair, more where the function collided by accident, one where it is injective. Nothing is asserted: the sum on the right is the sum of the numbers on the left. A cell in the before grid is an input, not an outcome, so selecting one explains what the collapse did to that input instead.

Pick a cell in either grid.

The equations, and what they pin down

Every surviving outcome y satisfies y · s = 0 over GF(2) — the XOR of the bits of s that y selects is zero. Each measurement is therefore one free linear equation about the secret. Not a hint, not a probability: an equation.

Measurements, in order

No measurements yet.

Row-reduced system

Empty.

Still consistent with everything measured

—

Why n−1 equations and not n

s = 0 satisfies y · s = 0 for every y, so the solution space always contains zero and can never shrink below one dimension. Rank n−1 leaves a two-element solution space {0, s}, and since a period is by definition non-zero, s is determined. Rank n would leave only {0} — which is the honest answer that the function has no period at all, and is exactly what the control target produces.

Measurements can repeat, and y = 0 is a perfectly legal outcome that carries no information. That is why the expected cost is n-and-a-bit queries rather than exactly n−1, and why the counter above tracks the wasted ones separately.

Count the queries

Both sides below are measured, not plotted. The classical attacker runs a real collision search against the same function table the circuit queries; the quantum side runs complete Simon rounds through the same simulator you have been pressing. Both count an oracle query the same way. Against a periodic target that collision search is a birthday search and the row says so; against the control there is no collision to find, the search reads the whole domain, and the row labels itself exhaustive instead — the birthday bound governs neither side of that comparison.

Not run yet.

Why the gap looks modest here and is catastrophic in reality

At n = 6 the classical attacker needs about 2³ = 8 queries and the quantum attacker about 7 — barely a difference, because √64 is small. The exponent is the whole story: at n = 128 the classical attacker needs about 2⁶⁴ ≈ 1.8 × 10¹⁹ queries and Simon needs roughly 130. The demo runs at a size you can watch, and the growth rates are what carry over.

130 queries does not mean 130 cheap operations. Each one is a coherent execution of the full keyed construction on a quantum computer — a reversible circuit for the cipher, with its gate count, depth and error-correction overhead, none of which this page models or counts. Query complexity is the quantity with the theorem attached; it is not gate complexity, and it is not wall-clock time.

Grover, Simon, Shor — three different threats

"Quantum breaks crypto" collapses three unrelated results into one sentence. They differ in what they need, what they give, and what you do about them.

Grover, Simon and Shor compared across five properties
	Grover	Simon	Shor
What it needs	Nothing. Any searchable predicate.	A hidden XOR period — internal structure.	Periodicity over the integers.
Speedup	Quadratic: 2ⁿ → 2^n/2	Exponential: 2^n/2 → O(n)	Exponential: sub-exponential → polynomial
Typical victim	AES-128 key search (→ 2⁶⁴ work)	Even-Mansour, CBC-MAC, 3-round Feistel, slide attacks	RSA, finite-field and elliptic-curve Diffie-Hellman
The fix	Double the key length.	Doubling buys nothing exponential — Simon's cost is O(n), so twice the width is about twice the queries, not 2ⁿ times as many. Remove the structure.	Replace the primitive outright — lattices, codes, hashes.
Access needed	Offline; the predicate is yours to evaluate.	Superposition queries to the keyed primitive (Q2). The strongest assumption of the three, and the honest caveat.	Offline; the public key is public.

What this actually breaks

Simon's algorithm is not a curiosity that happens to have a cryptographic application. Between 2010 and 2016 it was turned into a general tool against symmetric constructions, and the pattern is always the same: find a function built from the primitive whose period is the secret. The access assumed is also always the same: every attack below needs superposition queries to the keyed primitive — the Q2 model, which Limits takes apart.

Implemented in this demo: live above
Even-Mansour

E(x) = P(x ⊕ k₁) ⊕ k₂. Set f(x) = E(x) ⊕ P(x); its period is k₁. Classically secure to 2^n/2; quantum-broken in O(n).

Kuwakado & Morii, ISITA 2012
Implemented in this demo: live above
CBC-MAC and its relatives

f(b, m) = MAC(α_b ‖ m) has period (1, Eₖ(α₀) ⊕ Eₖ(α₁)). Recovering it is an existential forgery. The same argument reaches PMAC, GMAC, OCB and GCM.

Kaplan, Leurent, Leverrier & Naya-Plasencia, CRYPTO 2016
Described, not implemented: described only
3-round Feistel

Fix two distinct left inputs α₀, α₁ and define f(b, x) from the left half of the output XOR α_b. The period reveals the round-function difference and distinguishes the Feistel from a random permutation in O(n) — a construction proved secure classically by Luby-Rackoff.

Kuwakado & Morii, ISIT 2010
Described, not implemented: described only
Slide attacks

A cipher with identical rounds and a self-similar key schedule satisfies a slide relation. Written as a period, the classical 2^n/2 slide attack becomes polynomial — the clearest case of "structure that was merely a weakness becomes fatal".

Bonnetain, Naya-Plasencia & Schrottenloher, 2019

What survives

The countermeasure is not longer keys — Simon does not care how long k₂ is. It is removing the algebraic self-similarity the period rides on: more rounds with independent subkeys, a key schedule that is not self-similar, domain separation so that no attacker-controlled function of the primitive is periodic, and modes whose masks are not simple XOR offsets. A pseudorandom permutation with no exploitable structure has no period to find, which is exactly what the control target on this page demonstrates. None of these is a proof on its own — each removes the particular structure the known attacks ride on, and a construction is only Q2-secure once it has been analysed in that model.

What this demo does not prove

No quantum hardware is involved. Everything here is a full classical statevector simulation — real Hadamards, a real unitary oracle, 2^n+m real amplitudes held in one Float64Array. There is no imaginary part, because every gate in Simon's circuit has real entries and nothing here ever populates one; the arithmetic in the panel above is literally the numbers in that array. The oracle itself is a shortcut a real attacker does not get: the browser evaluates f's complete 2ⁿ-entry truth table up front and implements U_f as a table lookup, where a real Q2 attack would need a reversible quantum circuit for the keyed primitive — that circuit's synthesis and gate cost are not modelled or counted here. Accurate does not mean scalable: the cost of this simulation doubles with every qubit, which is precisely why a real quantum computer would be needed at cryptographic sizes.
The simulation is amplitude-level, and it is not a shortcut. For a function that satisfies Simon's promise exactly, the algorithm's output distribution is uniform over s⊥ and can be sampled classically in one line — so a "simulation" of the textbook case teaches nothing. This demo does not take that shortcut, because Even-Mansour's function usually collides by accident on top of its period, which skews the distribution, and only an amplitude-level simulation reproduces that. Usually, not always: whether a given key produces an exactly 2-to-1 function is a fact about that key, so the target card computes it per instance and says so on the satisfies Simon's promise exactly row rather than letting this paragraph assert it. (At n = 4 exactly 2 of the 15 possible k₁ values do satisfy it.) What is exact here is the linear algebra of the circuit — every Hadamard and the oracle are applied as real unitaries to the full state, to floating-point precision.
The Q2 model is a strong assumption. These attacks need the attacker to query the keyed primitive in superposition: coherent black-box access to an oracle that encrypts (or MACs) a superposition of inputs and hands back the quantum state. The key never leaves the oracle — but someone must have implemented the keyed primitive on a quantum device the attacker can query coherently. No deployed system offers that today, and it may never be offered. Some of these attacks have weaker Q1 variants; most do not. The demo shows what breaks if that access exists, and that is the honest framing.
Not production cryptography. A 4-to-6-bit block cipher is broken by definition; the whole codebook fits on screen. The point is that the attack's cost grows like n while the classical attack's grows like 2^(n/2), and that gap is real at every size.
Only two of the four listed breaks are implemented. Even-Mansour and CBC-MAC run live above, with the recovered key and the forged tag checked against the real construction. The 3-round Feistel distinguisher and the quantum slide attack are described and cited, not built.
Simon's algorithm can be wrong, and this demo checks. The linear system can name a candidate that is not a period. Every candidate is verified against f over the whole domain before it is reported, and a candidate that fails is rejected on screen rather than quietly retried.

What this is