up:: Breaking Today’s Cryptography MOC

Offline Simon’s Algorithm

The offline Simon’s algorithm is a quantum cryptanalysis technique, published by Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki, and André Schrottenloher at ASIACRYPT 2019, that runs Simon’s period-finding subroutine inside a Grover search so an attacker can break certain symmetric constructions using only ordinary classical queries plus offline quantum computation. Its importance is the attack model rather than a wider blast radius. Earlier Simon-based breaks needed the target to answer queries in quantum superposition, an access no deployed system grants, and the offline version removes that requirement to land the same style of attack in a model a real adversary could reach. It touches specific designs like Even-Mansour and the FX cipher family, and it leaves AES and mainstream symmetric cryptography untouched.

The short version:

• The offline Simon’s algorithm reworks the classic quantum symmetric attacks so they need only classical queries to the target, the realistic “Q1” model, instead of the superposition queries the original attacks assumed.
• It works by running Simon’s period-finding as a subroutine inside a Grover search, reusing one prepared quantum state across every Grover iteration rather than re-querying the target.
• It breaks the Even-Mansour construction in quantum time about 2^(n/3) with about 2^(n/3) classical queries and only O(n^2) qubits, and it extends to the FX construction and some Sponge authenticated modes (Bonnetain et al., ASIACRYPT 2019).
• The scope is narrow and honest. It hits single-permutation and key-whitening designs, the family behind ciphers like DESX, PRINCE, and PRIDE, and it does nothing to AES or to symmetric cryptography as a whole.
• It still needs a large fault-tolerant quantum computer, the same hardware class a Grover exhaustive search needs, which does not exist yet. Its value today is a design lesson, that some symmetric structures owe a quantum attacker more than Grover’s square-root discount.

An everyday way to picture it

Imagine a safecracker who has heard that a certain lock has a hidden flaw. To exploit the flaw the old way, she would have to ask the lock a magical kind of question, one that is somehow about every possible combination at the same time, and get a blended answer back. No real lock answers questions like that, so the attack stayed on paper.

The offline Simon’s algorithm is the version where she only ever asks the lock normal questions, one combination at a time, and writes down the plain answers. Then she takes that notebook home to her quantum workshop and does the clever interference trick privately, on her own gear. The lock never had to do anything unusual. That shift, from a magic question the lock must cooperate with to plain questions plus private quantum work, is the whole contribution.

What is the offline Simon’s algorithm?

The offline Simon’s algorithm is a way to mount a Simon-style period-finding attack against a keyed cryptographic construction while making only classical queries to that construction. Cryptographers sort quantum attacks into two models. In the Q2 model, the attacker may query the secret-keyed primitive on a quantum superposition of inputs and receive a superposition of outputs. In the Q1 model, the attacker makes ordinary classical online queries and does all quantum work offline on their own hardware. The Q2 model produces spectacular results, because Simon’s algorithm recovers a hidden key-period in roughly n superposition queries, yet those results assume an access real deployments never expose. The Q1 model is the realistic one, and it is where this algorithm operates.

The construction that makes the cleanest example is the Even-Mansour construction, a minimal block cipher defined as E(x) = P(x XOR k1) XOR k2, where P is a public permutation and k1, k2 are secret whitening keys. Kuwakado and Morii showed in 2012 that if you can query E in superposition, the function f(x) = P(x) XOR E(x) hides the period k1, and Simon’s algorithm reads it out in polynomial time. That is a total break, but only in Q2. The offline Simon’s algorithm gets a break in Q1, at a cube-root cost rather than polynomial, which is the honest price of dropping the superposition assumption.

Source: Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki, André Schrottenloher, “Quantum Attacks Without Superposition Queries: the Offline Simon’s Algorithm,” ASIACRYPT 2019, LNCS 11921, pp. 552–583, IACR ePrint 2019/614, arXiv:2002.12439.

How does the offline Simon’s algorithm work?

The core trick is to prepare Simon’s period-finding state one time from classical data, then reuse that same state inside every step of a Grover search, so the expensive online part happens once instead of once per guess. Here is the shape of it against Even-Mansour, without the math:

1. Split the key and set up a Grover search over the hard part. The attack guesses the top two-thirds of the whitening key k1 with a Grover search, which is what supplies the 2^(n/3) cost. The remaining structure is what Simon’s subroutine resolves.
2. Build one Simon state from purely classical queries. Define a smaller function g by fixing part of the input and querying the cipher classically for every value of a one-third-length input, about 2^(n/3) classical queries. Loading those classical answers into a quantum register prepares a Simon-style superposition state, the “offline” state, without any superposition query to the target.
3. Reuse that state on every Grover iteration. For each candidate guess Grover tests, the algorithm checks whether the guess is correct by running Simon’s period test against the already-prepared offline state. Because the state is reused rather than rebuilt, no fresh queries are needed inside the loop. This reuse is the insight that Kuwakado, Morii, Leander, and May’s earlier work lacked in the classical-query setting.
4. Read out the key. When Grover converges on the correct partial key, Simon’s linear-algebra step yields the rest, and the full key falls out with about 2^(n/3) classical queries and about 2^(n/3) offline quantum operations.

The two ways the authors describe their own idea are worth keeping. One framing is that they reuse a single set of superposition-derived queries across the whole Grover iteration instead of re-querying each time. The other is that they remove the large classical memory that a comparable collision-search attack would need, trading it for the algebraic structure Simon’s algorithm exploits. Both describe the same mechanism, and both explain why the qubit count stays modest at O(n^2).

Source: Bonnetain et al., ASIACRYPT 2019, IACR ePrint 2019/614.

Why is the offline Simon’s model more realistic than the original attacks?

Because it drops the one assumption that kept the earlier attacks theoretical, that an attacker can run your secret-keyed algorithm on quantum superpositions of chosen inputs. A superposition query means the target device itself evaluates its keyed function coherently across many inputs at once and hands back a quantum state, and a normal endpoint does not behave that way. Your cipher takes classical inputs, holds the key on classical hardware, and returns classical outputs. That mismatch is why the Simon-based breaks of MACs and modes catalogued by Kaplan and colleagues in 2016, real and complete in the Q2 model, stayed off the practical threat list.

The offline Simon’s algorithm changes the calculus by requiring only classical online access. An adversary who can collect plaintext-ciphertext pairs the ordinary way, then take that data to a quantum computer under their own control, has everything the attack needs. The cost of realism is a slower attack, cube-root time instead of polynomial, but the barrier that made the old attacks academic is gone. This is the reason the result mattered enough to name a technique after it, and the reason symmetric-primitive designers now weigh Q1 quantum security rather than dismissing quantum symmetric attacks as an artifact of an impossible model.

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.

What does the offline Simon’s algorithm actually break?

It breaks constructions whose security rests on a secret key hidden as a period inside a single public permutation or a whitening layer, and it improves prior quantum attacks on them. The two headline targets are the Even-Mansour cipher and the FX construction, with additional reach into some Sponge-based authenticated-encryption modes and a handful of related designs. The FX construction is the important one for real ciphers, because FX(P) = k2 XOR F_k(k1 XOR P) is exactly how key-whitening protects a block cipher, and it generalizes Even-Mansour by replacing the public permutation with a keyed cipher F. Ciphers built on FX-style whitening include DESX (Rivest’s hardening of DES against exhaustive search), and the lightweight ciphers PRINCE and PRIDE.

The algorithm’s contribution against these targets is a better cost in the realistic model, and, as a second result, a way to cut the amount of superposition access some Q2 attacks need down to a polynomial number of queries. The verified comparison, drawn from the paper’s own Table 1, makes the tradeoffs concrete (n is the block size, m the inner key length, and m = O(n)):

Target	Attack model	Online queries	Quantum time	Qubits	Source
Even-Mansour	Q2 (superposition queries)	~n superposition	polynomial	polynomial	Kuwakado-Morii 2012
Even-Mansour	Q1 (classical queries)	~2^(3n/7)	~2^(3n/7)	polynomial	Hosoyamada-Sasaki 2018
Even-Mansour	Q1 offline Simon	~2^(n/3)	~2^(n/3)	O(n^2)	this paper
FX	Q2 (Grover Meets Simon)	~n·2^(m/2) superposition	~2^(m/2)	polynomial	Leander-May 2017
FX	Q2 offline Simon	~n superposition	~2^(m/2)	polynomial	this paper
FX	Q1 offline Simon	~2^((m+n)/3)	~2^((m+n)/3)	polynomial	this paper

The pattern to read off the table is the point. Against Even-Mansour, the offline algorithm matches the best Q1 query count at 2^(n/3) while collapsing the qubit and memory needs to polynomial, and against FX it delivers the first classical-query attack that inherits Simon’s structure. It builds directly on Leander and May’s “Grover Meets Simon,” which first combined the two algorithms but still needed superposition queries.

Sources: Bonnetain et al., ASIACRYPT 2019, Table 1, IACR ePrint 2019/614. Gregor Leander, Alexander May, “Grover Meets Simon, Quantumly Attacking the FX-construction,” ASIACRYPT 2017, IACR ePrint 2017/427.

Does the offline Simon’s algorithm break AES or symmetric cryptography broadly?

No, and this is the misconception worth killing on sight. AES is a keyed substitution-permutation network, not an Even-Mansour or FX construction, so it hides no single whitening period for Simon’s subroutine to extract, and the offline Simon’s algorithm has nothing to grab onto. The same holds for the broad body of standard symmetric cryptography. The technique is a precise instrument aimed at designs with a specific algebraic shape, mostly minimalist single-permutation ciphers and key-whitening layers, several of which are lightweight or legacy.

For mainstream symmetric primitives, the quantum threat that actually governs key-size guidance is still Grover’s algorithm, which only halves effective strength and is answered by a larger key. AES-256 keeps a comfortable margin, and appropriately sized hashes like SHA-256 and SHA-384 stay useful. The offline Simon’s algorithm does not move that guidance. What it moves is how carefully designers of new constructions treat quantum structural attacks, because a design that leaks a period is now exploitable in a model that a real adversary can occupy.

Why does this matter if it doesn’t break a mainstream cipher?

It matters because it is the clearest evidence that quantum symmetric attacks deserve analysis beyond Grover’s square-root discount, even for a world of classical-only queries. Before this result, a defender could reasonably file all the Simon-based symmetric breaks under “impossible model” and move on. The offline Simon’s algorithm shows that the underlying period-finding leverage survives the move to the realistic Q1 setting for the constructions that carry the right structure, which means the realistic model still leaves those designs exposed.

Two practical consequences follow:

1. It sharpens the public-key-first framing. The result reinforces why post-quantum cryptography is overwhelmingly a public-key story while symmetric primitives still get scrutinized in quantum threat models rather than waved through.
2. It flags a narrow legacy harvesting concern. Long-lived data protected by older Even-Mansour or FX-style symmetric designs, the kind that lingers in legacy IoT, operational-technology controllers, and aging network gear, is a smaller and nearer-timeline exposure than the Shor-driven public-key break, and it belongs on the map when an estate contains those primitives.

This is the caveat that keeps a harvest-now-decrypt-later assessment honest about symmetric edge cases.

Common misconceptions

1. “The offline Simon’s algorithm breaks AES.” It does not. AES is neither an Even-Mansour nor an FX construction, so it exposes no whitening period, and the technique cannot touch it. The mainstream quantum concern for AES remains Grover’s, fixed by using AES-256.
2. “It makes symmetric cryptography quantum-broken.” It affects a specific family of single-permutation and key-whitening designs, several of them lightweight or legacy. The broad symmetric ecosystem is unaffected.
3. “It is a polynomial-time break like the original Simon attacks.” The realistic Q1 version costs about 2^(n/3) time and queries for Even-Mansour, a cube-root attack, rather than the polynomial cost the superposition-query attacks enjoyed. Dropping the unrealistic model has a price.
4. “It runs on today’s quantum computers.” It needs a large fault-tolerant quantum computer, the same hardware class a Grover exhaustive search requires, which does not yet exist. The result is a cryptanalytic and design advance, not a live capability.
5. “It needs superposition queries like the attacks it improves on.” The whole point is the opposite. It requires only classical online queries and does the quantum work offline, which is what makes the attack model realistic.

Questions people ask

Who published the offline Simon’s algorithm and when? Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki, and André Schrottenloher, at ASIACRYPT 2019, in a paper titled “Quantum Attacks Without Superposition Queries: the Offline Simon’s Algorithm” (IACR ePrint 2019/614). It builds on Leander and May’s 2017 “Grover Meets Simon.”

What is the difference between the Q1 and Q2 attack models? In the Q2 model the attacker queries the secret-keyed primitive on quantum superpositions of inputs, which real systems do not allow. In the Q1 model the attacker makes only classical online queries and does all quantum computation offline. The offline Simon’s algorithm operates in the realistic Q1 model.

Does it break the Even-Mansour cipher? Yes, with about 2^(n/3) classical queries, about 2^(n/3) offline quantum time, and only O(n^2) qubits for an n-bit block (IACR ePrint 2019/614). That improves the qubit and memory needs of the prior classical-query attack while matching its query count.

Which real ciphers use the FX construction it attacks? FX-style key whitening appears in DESX, which hardened DES against exhaustive search, and in the lightweight block ciphers PRINCE and PRIDE. The FX construction generalizes Even-Mansour by wrapping a keyed cipher in two whitening keys.

Is my AES-encrypted data at risk from this? No. AES is not an Even-Mansour or FX construction, so the algorithm cannot attack it. Your AES exposure, if any, is the modest Grover key-search discount, handled by using a 256-bit key.

Does it need a quantum computer that exists today? No. It requires a fault-tolerant quantum computer at the scale a Grover exhaustive search needs, which no one has built. The contribution is theoretical and forward-looking, sharpening how designers reason about quantum structural attacks.

How does it relate to plain Simon’s algorithm and to Grover’s? It runs Simon’s period-finding subroutine inside a Grover search, using Simon to resolve the hidden key-period and Grover to cover the part with no exploitable structure. The fusion is what lets it work with classical queries alone.

Should this change how I handle post-quantum migration? For almost every organization, the migration remains a public-key story driven by Shor’s algorithm, and symmetric guidance still follows Grover. The one place to look is legacy gear built on Even-Mansour or FX-style symmetric designs holding long-lived data, a narrow edge case worth noting in an inventory.

---

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 a legacy edge case 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.