up:: Breaking Today’s Cryptography MOC
Simon’s Algorithm
Simon’s algorithm is a quantum algorithm, published by Daniel Simon in 1994, that finds a hidden period inside a function using only about n quantum queries where a classical computer needs about 2^(n/2). It was the first result to prove that a quantum computer can be exponentially faster than any classical computer, including a randomized one, on a structured problem, and it directly inspired Shor’s algorithm a few months later. Its cryptographic reach is narrow and specific. It does not threaten public-key cryptography the way Shor’s does, and its symmetric-crypto attacks only work in a strong theoretical model where an attacker can query a secret-keyed function in quantum superposition, which is why it is not the main real-world worry.
The short version:
- Simon’s algorithm solves one artificial-but-important task, finding a hidden period
sin a function that repeats with that period, using aboutnquantum queries versus roughly2^(n/2)classical ones. That’s an exponential separation. - It was the first proof of an exponential quantum speedup over probabilistic classical computation, published by Daniel Simon in 1994 (SIAM J. Comput. 1997).
- It’s the reason Shor’s algorithm exists. Shor took Simon’s period-finding idea and moved it from the parity groups Simon used to ordinary integers, which is what let it break RSA and elliptic-curve cryptography.
- Its practical crypto relevance is much narrower than Shor’s. It can forge certain symmetric MACs and break some authenticated-encryption modes (Kaplan et al., 2016), but only in the quantum-query model, where the attacker gets to run your keyed algorithm on quantum superpositions of inputs.
- Real deployments don’t hand an attacker a superposition oracle over a secret key, so everyday AES and SHA-256 are not endangered by Simon’s algorithm. The honest verdict is a precise, model-dependent threat, not a broad one.
An everyday way to picture it
Imagine a very long hallway of numbered doors, and behind each door is a colored card. You’re promised the colors repeat on a fixed stride: door 1 and door 1 plus the secret stride show the same color, and so does every pair separated by that stride. Your job is to find the stride. Classically you’d have to open door after door, comparing colors, until you stumbled on two that match, and with a huge hallway that takes a punishing number of tries. Simon’s algorithm opens every door at once in superposition, lets the matching colors interfere with each other, and reads out a clue about the stride in a single pass. Do that a handful of times, combine the clues with grade-school algebra, and the secret stride falls out. The hallway can be astronomically long and it barely changes the effort.
What is Simon’s problem?
Simon’s problem is the specific task Simon’s algorithm was built to solve, and it’s a “promise problem,” meaning you’re guaranteed something about the input up front. You’re given a function f that takes n-bit strings to outputs, with a promise: there’s a hidden secret string s (not all zeros) such that f(x) equals f(y) exactly when y is x or x XOR s. In plain terms, the function is two-to-one, and every colliding pair of inputs is separated by the same hidden value s. The goal is to recover s.
In the language of group theory, this is the hidden subgroup problem over the group of bit-strings under XOR, which mathematicians write as (Z/2)^n. That framing matters because it’s the exact same shape of problem Shor’s algorithm solves, just over a different group. Simon works over parity (XOR) groups; Shor works over the integers. Naming the connection is the whole reason Simon’s algorithm is historically load-bearing.
Source: Daniel R. Simon, “On the Power of Quantum Computation,” Proc. 35th FOCS, 1994, pp. 116–123, and SIAM Journal on Computing 26(5), 1997, pp. 1474–1483, epubs.siam.org.
How does Simon’s algorithm work?
Simon’s algorithm finds the hidden period by turning the function’s built-in collisions into linear equations about s, then solving them. It never opens doors one at a time. Here’s the shape of it, without the math:
- Build a superposition of every input. Put a register of
nqubits into a superposition that holds all2^npossible input strings at once, each with equal weight. - Evaluate the function once, over all inputs. Apply
fto the whole superposition in a single pass, so the machine now holds every input paired with its output simultaneously. - Collapse to a colliding pair. Measuring (or discarding) the output register leaves the input register in a superposition of exactly two strings, some
xand its partnerxXORs. Both stay hidden from you, yet the machine holds the fact that they differ by the secret. - Interfere and measure. Apply a layer of Hadamard gates, which is the quantum Fourier transform for parity groups, and measure. The result is always a string
ythat is guaranteed to have an even overlap withs, meaningyandssatisfy one linear equation over the parity field. - Repeat and solve. Run the whole thing about
ntimes to collect roughlynindependent equations, then solve that small linear system with ordinary Gaussian elimination to pin downs.
The intuition worth keeping is that quantum interference lets each run leak one honest linear constraint about the secret, so a handful of runs plus schoolbook algebra recovers a period that classical search would need exponentially many probes to find. That’s why the speedup is exponential rather than incremental. It’s a different way of asking the question, and the same reframing is the engine inside Shor’s algorithm.
Source: Simon, SIAM J. Comput. 26(5), 1997, epubs.siam.org.
Why is Simon’s algorithm historically important?
Simon’s algorithm is important because it was the first proof that a quantum computer can beat every classical computer exponentially, including a classical computer allowed to flip coins, on a genuine structured problem. Earlier results hinted at quantum advantage but fell short of that bar. The Deutsch-Jozsa algorithm (1992) showed an exponential gap only against deterministic classical machines, and a randomized classical machine erased it by guessing. Simon’s problem is different. A classical computer needs on the order of 2^(n/2) queries even when it’s allowed to guess and accept a small error probability, while Simon’s algorithm needs only about n. That’s a true exponential separation in the query model, and it was the concrete evidence that quantum computing might be more than a curiosity.
The caveat that keeps this gotcha-proof is that the separation is an oracle separation. It’s proven relative to a black-box function you can only probe by querying, which is the right and standard way to state it. It is not a claim that quantum computers unconditionally solve some classical-hard problem in general, a question that remains open. Within the query model, though, the gap is real, proven, and exponential.
Source: Simon, “On the Power of Quantum Computation,” FOCS 1994 / SIAM J. Comput. 1997, epubs.siam.org.
How did Simon’s algorithm inspire Shor’s algorithm?
Shor built directly on Simon’s idea, and he said so. Simon circulated his result in early 1994, and within months Peter Shor recognized that the same machinery, superposition, a single evaluation of a periodic function, and interference through a quantum Fourier transform, would work over the integers instead of over parity strings. Simon’s algorithm finds a hidden period in the XOR group (Z/2)^n; Shor’s algorithm finds a hidden period in modular arithmetic, which is exactly what factoring and the discrete logarithm reduce to. Swapping the parity Fourier transform (a layer of Hadamard gates) for the Fourier transform over Z_N is the essential upgrade that carried period-finding from a toy promise problem to a break on RSA, Diffie-Hellman, and elliptic-curve cryptography.
So the lineage is tight. Simon proved the principle on an artificial problem, and Shor pointed the same principle at the math that secures the internet. The published record reflects it, with Shor’s factoring paper crediting Simon’s work as the starting point for the quantum period-finding approach.
Source: Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Comput. 26(5), 1997, arXiv:quant-ph/9508027.
Does Simon’s algorithm threaten symmetric cryptography?
Yes, but only for specific constructions and only in a strong theoretical model. In 2016, Kaplan, Leurent, Leverrier, and Naya-Plasencia showed that Simon’s period-finding turns several symmetric constructions from “secure” into “completely broken,” because those constructions hide a secret period that Simon’s algorithm can extract. The trick is that finding a collision in these schemes classically takes about 2^(n/2) queries, but when the collisions carry a hidden periodicity, Simon’s algorithm finds the period, and the key, with only about n queries. That’s an exponential speedup, the same one Simon proved in 1994, aimed at message authentication and authenticated encryption.
The constructions the paper breaks in this model include:
| Construction | Type | Status under Simon’s algorithm |
|---|---|---|
| CBC-MAC | Message authentication | Completely broken (forgery) |
| PMAC | Message authentication | Completely broken (forgery) |
| GMAC / GCM | Authentication / authenticated encryption | Completely broken |
| OCB | Authenticated encryption | Completely broken |
| Even-Mansour cipher | Block-cipher construction | Key recovered in polynomial time |
| CLOC, AEZ, COPA, OTR, POET, OMD, Minalpher | CAESAR-competition candidates | Broken in the same model |
The same paper also gives an exponential speedup to the classical “slide attack” against iterated ciphers. The critical qualifier on all of it is the attack model, covered next.
Source: Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia, “Breaking Symmetric Cryptosystems using Quantum Period Finding,” CRYPTO 2016 (LNCS 9815, pp. 207–237), arXiv:1602.05973.
Is Simon’s algorithm a real-world threat today?
For everyday symmetric cryptography, no, and the reason is the attack model. Every one of the Kaplan et al. breaks lives in what cryptographers call the quantum-query (or “Q2”) model, where the attacker can query the secret-keyed primitive on a quantum superposition of chosen inputs and get back a superposition of outputs. Real systems don’t work that way. Your MAC or your AES-GCM endpoint takes classical inputs, holds the key on classical hardware, and returns classical outputs, so an outside attacker has no superposition oracle to run Simon’s algorithm against. Without that oracle, these particular attacks don’t launch.
That makes Simon’s algorithm a precise and model-dependent concern rather than a broad one, and the contrast with Shor’s algorithm is the point. Shor breaks public-key cryptography using only the public key, so it needs no special access to anything secret, which is exactly why it drives the whole post-quantum migration. Simon-based symmetric attacks need a capability that standard deployments don’t expose.
There is active research on relaxing the assumption, notably the “offline Simon” line of work that reduces how much superposition access is required, and it’s a reason to design new symmetric primitives with quantum-query security in mind and to prefer larger internal states. That’s a design concern for future primitives, not evidence that a quantum computer will forge your existing AES-based traffic. The mainstream symmetric-crypto quantum threat remains Grover’s algorithm, which only halves security and is fixed by a bigger key.
Source: Kaplan, Leurent, Leverrier, Naya-Plasencia, CRYPTO 2016, arXiv:1602.05973.
Simon’s, Shor’s, and Grover’s compared
The three algorithms people meet first in quantum cryptography sit in very different places, and keeping them straight is most of the battle:
| Property | Simon’s algorithm | Shor’s algorithm | Grover’s algorithm |
|---|---|---|---|
| Published | Daniel Simon, 1994 | Peter Shor, 1994 | Lov Grover, 1996 |
| Solves | Hidden period over parity groups | Factoring and discrete logs | Unstructured search |
| Speedup | Exponential (query model) | Exponential | Quadratic (square-root) |
| Main significance | First proof of exponential quantum advantage | Breaks public-key crypto | Halves symmetric strength |
| Crypto impact | Narrow, symmetric, quantum-query model only | Total break of RSA, ECC, DH | Bigger keys for AES and hashes |
| Real-world threat now | Low (needs a superposition oracle) | High once a CRQC exists | Manageable with larger parameters |
Sources: Simon, epubs.siam.org; Shor, arXiv:quant-ph/9508027; Grover, arXiv:quant-ph/9605043.
Common misconceptions
- “Simon’s algorithm breaks RSA or AES.” It does neither. It solves a hidden-period promise problem, and its only cryptographic bite is against certain symmetric MACs and modes in the quantum-query model. Public-key breaking is Shor’s job, and symmetric key-size pressure is Grover’s.
- “Simon’s attacks mean AES-GCM is quantum-broken in practice.” They mean it’s broken if an attacker can query the keyed primitive in superposition, which real deployments don’t allow. On classical inputs, those systems are fine against Simon’s algorithm.
- “Simon’s algorithm was the first quantum algorithm to beat classical computers.” It was the first to beat probabilistic (randomized) classical computers exponentially. The earlier Deutsch-Jozsa result only beat deterministic classical machines, and randomization erased that gap.
- “Simon’s problem is a real cryptographic problem someone needs to solve.” It’s a deliberately artificial promise problem, engineered to demonstrate a separation. Its value is the proof and the technique, which Shor then turned on real cryptography.
- “Simon’s and Shor’s are unrelated algorithms.” They’re the same idea over different groups. Simon does period-finding over parity strings; Shor does it over the integers, which is the change that made it break public-key cryptography.
Questions people ask
What does Simon’s algorithm actually do?
It finds a hidden period s in a function that’s promised to collide exactly on inputs separated by s. It needs about n quantum queries where a classical computer needs roughly 2^(n/2), which is an exponential speedup for that task.
Who invented Simon’s algorithm and when? Daniel Simon, then at the Université de Montréal, presented it at the 1994 IEEE Symposium on Foundations of Computer Science, with the journal version in SIAM Journal on Computing in 1997 (epubs.siam.org). It predates the published version of Shor’s algorithm and inspired it.
Why does Simon’s algorithm matter if the problem is artificial? Because it was the first hard proof that quantum computers can be exponentially faster than any classical computer on a structured problem, and because its period-finding technique is the direct blueprint for Shor’s algorithm, which does break real cryptography.
Does Simon’s algorithm break message authentication codes? It breaks specific ones, including CBC-MAC, PMAC, and GMAC, but only in the quantum-query model where the attacker can run the keyed MAC on quantum superpositions of inputs (arXiv:1602.05973). Standard deployments don’t expose that access, so it isn’t a live threat to those MACs as normally used.
What’s the difference between Simon’s algorithm and Shor’s algorithm? They use the same period-finding machinery, but over different structures. Simon works over parity (XOR) groups and solves an artificial problem, while Shor works over modular arithmetic and solves factoring and discrete logs, which is what breaks RSA and ECC.
Should I change my symmetric cryptography because of Simon’s algorithm? For most systems, no. The mainstream quantum guidance for symmetric crypto is driven by Grover’s algorithm, so use AES-256 and appropriately sized hashes. Simon-based attacks matter mainly to designers building new primitives that should be secure even against superposition queries.
Does a quantum computer exist that can run Simon’s algorithm usefully against crypto? No. Beyond needing fault-tolerant quantum hardware that doesn’t yet exist at scale, the symmetric attacks also need a superposition oracle over a secret key, which real systems don’t provide. Both barriers stand between the theory and any practical break.
Everything here is the map, given freely. When your team needs the quantum-crypto threat sorted into what’s urgent, what’s narrow, and what’s noise for your own systems, that’s the work I do. Request an alignment briefing.
Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.