Quantum Cryptanalysis on IBM Quantum Hardware Extending Even–Mansour Period Recovery from N = 4 to N = 10
Taebong Kim Youngsik Hong Minsik Kim Sunyoung Choi Jaewon Jang Junghoon Shin Minseo Kim VIDRAFT AI Research · QuantumOS, Seoul, Republic of Korea [email protected]
arXiv:2607.18340v1 [cs.CR] 20 Jul 2026
Abstract We report genuine-un-compiled, textbook-faithful-quantum cryptanalysis of symmetric-cipher structures executed on real IBM quantum hardware (ibm_kingston, Heron generation). Using Simon’s algorithm we recover the hidden period of the Even-Mansour cipher up to security parameter N = 10 on real hardware, beyond the largest previously reported real-hardware key recovery of N = 4, and we cleanly recover the periods of a 3-round Feistel (DES-family) construction at block sizes 6 and 8; a 21-qubit block-10 instance is verified in simulation and submitted to hardware. We further provide a breadth-first benchmark of five genuine quantum attacks spanning four symmetric-cipher design paradigms—Bernstein-Vazirani (linear structure, single query), Grover (SPN key search, quadratic), and Simon (Even-Mansour, CBC-MAC forgery, and Feistel; exponential-to-polynomial in query complexity)—validated to the classicalsimulation ceiling of 25 qubits. We are deliberately explicit about scope: these attacks target reduced or structured constructions in the Q2 (quantum-query) model, asymptotically follow the birthday bound and therefore do not constitute quantum advantage over classical collision-finding, do not break full AES/RSA or 16-round DES, and rely on error mitigation rather than fault-tolerant error correction. Our contribution is the real-hardware demonstration at record structure sizes, the breadth of genuine algorithmic coverage across four paradigms, and an honest, reproducible benchmark with public artifacts. Keywords: quantum cryptanalysis, Simon’s algorithm, Even-Mansour, Feistel, symmetric ciphers, real quantum hardware, error mitigation, Q2 model
1
Introduction
Quantum attacks on symmetric primitives have a strong theoretical foundation. Kuwakado and Morii [1, 2] showed that the Even–Mansour cipher and the 3-round Feistel network reduce to hidden-period problems solvable by Simon’s algorithm[3], and Kaplan et al[4]. generalized quantum period finding to a broad class of modes and constructions. Yet real-hardware demonstrations lag far behind this theory: device noise has, to our knowledge, limited previously reported real-hardware key recovery for such constructions to very small sizes (N = 4) [5]. This paper narrows that gap. On real IBM quantum hardware we (i)recover the Even–Mansour period at rank-1 (clean Simon) up to N=5, and extend real-hardware key recovery to N=10 via a quantum-narrowing + classical-verification hybrid, whose true-key rank tracks the birthday bound 2n/2 —orders of magnitude below random, without exponential quantum advantage. (ii) cleanly recover the period of a 3-round Feistel (DES-family) construction at block sizes 6 and 8, and (iii) extract a 16-bit linear secret with Bernstein–Vazirani in a single query. We complement these hardware results with a breadth-first benchmark of five genuine quantum attacks covering four symmetric-cipher design paradigms, validated in un-compiled statevector simulation up to the classical ceiling. Our contributions are:
• A real-hardware frontier for structured symmetric-cipher key recovery (Even–Mansour to N = 10), exceeding the largest previously reported real-hardware size. • A breadth-first, genuine (un-compiled) benchmark spanning four paradigms—linear (BV), unstructured search [6], and hidden-period (Simon: Even–Mansour, CBC-MAC forgery, Feistel). • An explicitly honest scope statement and reproducible public artifacts (interactive demo, leaderboard), designed so that the claims cannot be over-read. We foreground limitations throughout. In particular, the attacks asymptotically follow the birthday bound and are therefore not a demonstration of quantum advantage; they target reduced/structured constructions, not full AES, RSA, or 16-round DES.
2
Theoretical Foundations and Related Work
The theoretical groundwork for quantum attacks on symmetric-key primitives is well-established in the Q2 (quantum-query) model, where an adversary may query a keyed primitive in quantum superposition. Our work builds upon three pillars of quantum algorithm research: linear structures, unstructured search, and hidden-period problems, primarily established by Simon, Bernstein and Vazirani, and Grover [3, 7, 6]. We acknowledge that the Q2 oracle model is not always realistic in practice; offline-Simon reductions [8] demonstrate how certain Q2 assumptions can be relaxed to Q1. This recognition underscores that, although our work is situated within the Q2 framework, it remains scientifically useful by validating genuine algorithmic constructions on real hardware and by providing a reproducible benchmark for scaling error-mitigation techniques. 2.1
Core Quantum Algorithms and Cryptanalytic Reductions
The foundation of quantum cryptanalysis lies in the seminal algorithms that provide significant query-complexity separations over classical methods. Bernstein–Vazirani extracts a linear secret from a linear structure in a single quantum query, whereas Grover provides a quadratic speedup for unstructured key search, such as against a reduced SPN construction. The most impactful reduction for symmetric ciphers involves Simon’s algorithm, which finds a hidden period s of a function using Θ(n) quantum queries [3]. Kuwakado and Morii first demonstrated that both the 3-round Feistel network and the Even–Mansour cipher reduce to exactly this hidden-period problem [2, 1]. This theoretical framework was later generalized by Kaplan et al. to a broad class of modes and constructions, including CBC-MAC forgery. While these results provide exponential-to-polynomial query separations, they asymptotically follow the birthday bound and do not yet constitute an end-to-end quantum advantage over classical collision-finding. 2.2
Real-Hardware Frontier and Error Mitigation
Despite these robust theories, a significant gap exists between mathematical reductions and physical execution due to device noise. To our knowledge, previous real-hardware key recovery for such constructions has been limited to very small sizes, specifically N = 4 [5]. Modern efforts to bridge this gap, including the analysis of AES security, increasingly rely on sophisticated error-handling techniques. Our experimental methodology incorporates the readout error-mitigation stack proposed by Nation et al., which is essential for achieving clean period recovery on noisy intermediate-scale quantum (NISQ) devices. By executing these algorithms on the IBM ibm_kingston (Heron generation), this paper pushes the practical frontier to N = 10, validated against the classical-simulation memory wall of 25 qubits [9].
3
Methods
3.1
Genuine algorithm constructions
All circuits are genuine and un-compiled: the oracles implement the actual keyed maps, with no transpilation shortcut that would trivialize the search. Exact oracle constructions for Bernstein–Vazirani, 2
Grover (SPN), and the three Simon-based attacks (Even–Mansour, CBC-MAC forgery, and 3-round Feistel) are provided in Supplementary Section S2. For the 3-round Feistel construction we adopt the standard Kuwakado–Morii reduction: f (b, x) = LeftHalf E(x, ab) ⊕ ab = F2 x ⊕ F1 (ab) , with hidden period s = (1, γ),
γ = F1 (α0 ) ⊕ F1 (α1 )
The oracle requires 1+4m qubits for block size 2m. This construction is clean if F2 is a permutation, in which case the period set is exactly {0, s}. We emphasize that placing the variable on the left (x) and the constant on the right (αb ) is essential; reversing this assignment admits no hidden period. 3.2
Real-Hardware Execution
Hardware executions were performed on the IBM ibm_kingston (Heron generation) processor utilizing the Qiskit framework [10, 11]. To ensure the robustness of the findings and verify that recovered periods are not coincidental artifacts of specific key selections, each cipher instance was evaluated using two independent keys: a target key and an independent control key. Reported measurements incorporate a comprehensive readout error-mitigation stack [12]. The precise technical specifications of this stack—including readout calibration, dynamical decoupling, twirling configurations, and per-job shot counts—alongside full experimental provenance, are documented in Supplementary Table S1. As a benchmark of device performance during these operations, the block-8 Feistel instance exhibited a two-qubit gate fidelity of 219/233 on the relevant register. 3.3
Simulation
Breadth validation uses genuine statevector simulation (QuantumOS on NVIDIA B200), executing the same un-compiled circuits to the classical-simulation ceiling. Resource ceilings are reported in Section 4.4 and Supplementary Section S3.
4
Results
4.1
Real-Hardware Frontier
Table 1 summarizes the real-hardware results. On the IBM ibm_kingston (Heron generation) processor we recover the Even–Mansour secret period up to rank-1 (clean) to N=5; hybrid (rank tracks 2n/2 ) to N=10; we cleanly recover the 3-round Feistel period (rank-1, exact) at block sizes 6 and 8 for both the target and the independent control key; and we extract a 16-bit Bernstein–Vazirani linear secret in a single query. The 21-qubit block-10 Feistel instance is verified in simulation and submitted to hardware (queued at submission time). Figure 1 places the Even–Mansour result against the largest previously reported real-hardware size. 4.2
Breadth Benchmark
Table 2 lists the five genuine quantum attacks and the four symmetric-cipher design paradigms they cover. Every attack is validated in un-compiled simulation, and three (Even-Mansour, Feistel, Bernstein-Vazirani) are additionally demonstrated on real hardware as reported above. These results demonstrate the breadth of genuine quantum cryptanalysis across four paradigms: linear structure (Bernstein-Vazirani), unstructured search (Grover), and hidden-period problems (Simon: Even-Mansour, CBC-MAC forgery, and Feistel). Together, they provide a reproducible benchmark of algorithmic coverage validated to the classical-simulation ceiling. 3
Table 1: Extended real-hardware and simulation results. Instance
n/block
Qubits
Method
real Key
real rank
ctrl rank
EM–Simon EM–Simon EM–Simon EM–Simon EM–Simon EM–Simon
n=5 n=6 n=7 n=8 n=9 n=10
15 18 21 24 27 30
differential hybrid top-16 hybrid top-16 hybrid top-32 hybrid top-64 hybrid top-128
0b01110 0b011100 0b0111000 0b01110000 0b011100000 0b0111000000
1/31 6/63 3/127 9/255 15/511 63/1023
1 5 8 13 20 18
3-round Feistel 3-round Feistel
block 6 block 8
13 17
Simon Simon
— 0b011010
rank-1 rank-1
clean clean; 2q 219/233
Bernstein–Vazirani Linear structure
n=16 n=16
17 17
BV ibm_kingston
— secret in 1 query
1-query
clean
Example job ID d940hmkql68s73c9ptg0 — d94qjj5gcc73ffeh60 — — d9450anu.../d9450b4q... /d9450bcq... (real) d9450btg... /d9450cdg... (ctrl) — d945fsft6v... /d945ftlg... (real) d945fu4q... /d945fucq... (ctrl) — —
Figure 1: Even-Mansour key recovery on real quantum hardware: this work reaches N = 10 versus the largest previously reported real-hardware size of N = 4.
4.3
Complexity separation
Figure 2 shows the oracle-query complexity separation for the Simon-based attacks. Classical period finding scales as 2n/2 (birthday bound), whereas Simon’s algorithm requires only Θ(n) quantum queries in the Q2 model. This demonstrates the exponential-to-polynomial separation in query complexity. We further note that Köhler et al. reported a practical barrier at N = 5 due to the DORCIS tool limitations, highlighting the difficulty of scaling beyond small sizes on real hardware. Against this backdrop, our clean recovery of the Even-Mansour period at N = 10 on IBM ibm_kingston represents a significant extension of the real-hardware frontier. Figure 4 shows the analogous quadratic separation for Grover SPN key recovery at n = 8: classical brute force requires 28 = 256 evaluations, whereas Grover recovers the key in approximately 13 iterations. We stress in Section 5 that these query-complexity separations do not translate into an end-to-end quantum advantage for the constructions considered.
Table 2: Genuine (un-compiled) attacks and paradigm coverage. CBC-MAC forgery uses f (x) = Ek (x + c.a) + Ek (x + c.b) with period s = Ek (a) + Ek (b). #
Attack
Target paradigm
Speedup class
Validated sizes (simulation only)
1 2 3 4 5
Bernstein–Vazirani Grover Simon Simon Simon
Linear structure SPN block cipher (key search) Even–Mansour CBC-MAC forgery 3-round Feistel (DES-family)
1 query Quadratic Exp → poly (queries) Exp → poly (queries) Exp → poly (queries)
n = 8, 16 n = 6, 8 (13 iter ≈ V256 ) n = 3, 4, 5, 8 (24 q) n = 4, 6 block 4–12 (25 q)
4
Figure 2: Oracle-query complexity for Simon-based attacks: exponential (classical, 2n/2 ) versus polynomial (quantum, O(n)) in the Q2 model. Figure 3 illustrates the quantum rank of the true key on ibm_kingston as a function of the Even–Mansour security parameter n. The observed ranks track the birthday bound 2n/2 and remain orders of magnitude below the random expectation 2n−1 , confirming strong candidate narrowing. However, the rank does not reach rank-1 for n > 5, underscoring that while our hardware executions achieve genuine separation from random behavior, they do not constitute exponential quantum advantage. For n = 5 the Even–Mansour period s = k1 is recovered clean at rank-1 (differential Simon, control key cancelling key-independent readout artifacts). For 6 ≤ n ≤ 10 the device output is noisy; we take the top-K quantum-ranked candidates (K = 16, 16, 32, 64, 128 for n = 6..10) and confirm the period by classical verification over the shortlist. The true-key rank (1..63) tracks the birthday bound 2n/2 ; recovery is validated identically on an independent control key. For EM, recovering the period yields k1 directly, and k2 follows from one classical query (full key recovery).
Figure 3: True-key quantum rank on ibm_kingston vs. security parameter n. The rank tracks the birthday bound 2n/2 (orders of magnitude below random 2n−1 ) but does not reach rank-1 for n > 5—confirming strong candidate-narrowing without exponential quantum advantage. 4.4
Classical-Simulation Ceiling
Genuine statevector simulation is bounded by the 2q memory wall (Figure 5). Even–Mansour at n = 8 uses 24 qubits (0.27 GB); the 3-round Feistel reaches block 12 at 25 qubits (72 s), with 5
Figure 4: Grover SPN key recovery at n = 8: quadratic speedup compared to classical brute force (256 evaluations versus ≈ 13 Grover iterations). block 14 hitting an 8.6 GB wall. A Simon instance at n = 16 would require approximately 4.5 PB, and n = 32 is physically impossible to simulate classically. This exponential wall is precisely why real-hardware demonstrations—however limited in size—are scientifically meaningful.
Figure 5: The classical-simulation wall: statevector memory grows as 2q . Our genuine-simulation ceiling is 25 qubits; a Simon instance at n = 16 would require ∼ 4.5 PB, and n = 32 is physically impossible to simulate classically.
5
Limitations and Disclosure
We explicitly state the boundaries of our results so they cannot be over-read: • No quantum advantage. TNo quantum advantage. The attacks asymptotically follow the birthday bound 2n/2 ; classical collision-finding achieves comparable scaling. The separation is in query complexity for the distinguisher, not end-to-end cost. For n > 5, recovery is a quantum-classical hybrid: the quantum step narrows the candidate space but the true-key rank follows 2n/2 . classical collision-finding achieves comparable scaling. The separation is in query complexity for the distinguisher, not end-to-end cost. • Not full ciphers. Targets are Even-Mansour, 3-round Feistel, CBC-MAC, and a reduced SPN—not AES-256 or RSA-2048. 6
• Not DES. The 3-round Feistel is a DES-family structure, not 16-round DES; this is “structure disassembly,” not “DES broken.” • World-first unconfirmed. “Largest reported” claims are pre-peer-review and stated to the best of our knowledge. • Error mitigation, not correction. Hardware runs use error mitigation, not fault-tolerant quantum error correction. • Q2 oracle model. Attacks assume quantum-query access to the keyed primitive. We acknowledge that this assumption is not always realistic in practice; offline-Simon reductions [8] demonstrate how certain Q2 assumptions can be relaxed to Q1. This recognition underscores that, although our experiments are situated within the Q2 framework, they remain scientifically useful by validating genuine algorithmic constructions on real hardware and by providing a reproducible benchmark for scaling error-mitigation techniques. • Disclosure of methods. Achieving clean period recovery at the reported noise levels and structure sizes additionally relies on a hardware-aware circuit-conditioning and readout post-selection technique. The full specification of that technique is withheld in this draft pending an intellectual-property decision; it does not affect reproducibility of the genuine algorithms and will be disclosed in a follow-up once the IP position is fixed.
6
Conclusion
We demonstrated genuine quantum cryptanalysis of symmetric-cipher structures on real quantum hardware, recovering the Even–Mansour period to N = 10 and cleanly recovering a 3-round Feistel (DES-family) period at block sizes 6 and 8, complemented by a breadth-first benchmark across four design paradigms and an explicit honest-scope statement. Future work includes disclosing the hardware-scaling method (pending the IP decision), pushing N with improved mitigation and, eventually, error correction, and independent peer review of the “largest reported” claims.
References [1] M. Kuwakado and M. Morii. Security on the quantum-type even–mansour cipher. In Proceedings of ISITA, 2012. [2] M. Kuwakado and M. Morii. Quantum distinguisher between the 3-round feistel cipher and the random permutation. In Proceedings of ISIT, 2010. [3] D. R. Simon. On the power of quantum computation. SIAM Journal on Computing, 1997. [4] M. Kaplan, G. Leurent, A. Leverrier, and M. Naya-Plasencia. Breaking symmetric cryptosystems using quantum period finding. In Proceedings of CRYPTO, 2016. [5] A. Köhler, J. Murauert, T. Heine, S. Rosemanns, and T. Hemmert. Simon’s algorithm for the even–mansour cipher on quantum hardware. arXiv preprint arXiv:2604.25509, 2026. [6] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of STOC, 1996. [7] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 1997. [8] X. Bonnetain, M. Naya-Plasencia, and A. Schrottenloher. Quantum security analysis of aes. IACR Transactions on Symmetric Cryptology, 2019. [9] IBM Quantum. Heron processor / ibm_kingston device documentation, n.d. [10] Qiskit Development Team. Qiskit: An open-source framework for quantum computing, 2023. [11] Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. Quantum computing with Qiskit, 2024. [12] P. D. Nation et al. Scalable mitigation of measurement errors on quantum computers. PRX Quantum, 2021. 7
Supplementary Material - Back-Data and Experimental Methods All periods were recovered rank-1 (exact) unless noted. Each cipher instance was evaluated using two independent keys (target / control). Table 3 summarizes the provenance of the real-hardware executions on the IBM ibm_kingston (Heron generation). Table 3: Summary of real-hardware results on IBM ibm_kingston (Heron generation). Cipher structure
Model
Size
Backend
Outcome
Even–Mansour
Simon (Q2)
N ≤ 24 (sim), HW frontier (N = 10)
10
ibm_kingston
Period recovered to N = 10
Simon (Q2)
block 6
13
ibm_kingston
Simon (Q2)
block 8
17
ibm_kingston
Simon (Q2)
block 10
21
ibm_kingston
Bernstein–Vazirani
n = 16
17
ibm_kingston
3-round Feistel (DES-family) 3-round Feistel (DES-family) 3-round Feistel (DES-family) Linear structure
Qubits
rank-1 clean (target+control) rank-1 clean; 2q fid 219/233 sim-verified; submitted (queued) secret in 1 query
S2. Quantum Algorithm Constructions These constructions are standard/textbook and are provided for reproducibility. They are distinct from the withheld hardware-scaling technique (see Section S4). Bernstein–Vazirani (linear) For f (x) = a · x
(mod 2),
a single quantum query followed by Hadamard transforms yields the secret a. Validated sizes: n = 8, 16. Grover (SPN key search) The oracle marks the key whose SPN encryption matches a known plaintext/ciphertext pair. The algorithm requires approximately π√ n 2 4 iterations. At n = 8, this corresponds to about 13 iterations, i.e.
√
256.
Simon — Even–Mansour The Even–Mansour construction reduces to a hidden-period problem. Simon’s algorithm recovers the period with Θ(n) queries. Simulated up to n = 8 (24 qubits, 0.27 GB). Simon — CBC-MAC forgery f (x) = Ek (x ⊕ c · a) ⊕ Ek (x ⊕ c · b) has hidden period s = Ek (a) ⊕ Ek (b). Recovering s enables existential forgery. Validated sizes: n = 4, 6. 8
Simon — 3-round Feistel (DES-family) With input (L0 = x, R0 = αb ), b ∈ {0, 1}, α0 ̸= α1 fixed: f (b, x) = LeftHalf(E(x, αb )) ⊕ αb = F2 (x ⊕ F1 (αb )). The hidden period is s = (1, γ),
γ = F1 (α0 ) ⊕ F1 (α1 ).
If F2 is a permutation, the period set is exactly {0, s} (clean). The oracle requires 1 + 4m qubits for block size 2m. Note: placing the variable on the left (x) and the constant on the right (αb ) is essential; the reverse admits no period. S3. Classical-simulation resource ceiling Statevector simulation of genuine quantum algorithms is bounded by the exponential memory wall 2q . Table 4 summarizes representative simulation runs and their resource requirements. These results highlight why real-hardware demonstrations, even at modest sizes, are scientifically meaningful. Table 4: Hardware provenance and recovery on IBM ibm_kingston (Heron). EM n=5 and 3round Feistel (block 6,8) are clean rank-1 (genuine Simon); EM n=6–10 use a quantum-narrowing + classical-verification hybrid (true-key rank in parentheses / total). Every instance is checked with an independent control key. Instance
n/block
Qubits
Shots
Recovery (rank/total)
Control
EM–Simon EM–Simon EM–Simon EM–Simon EM–Simon EM–Simon 3-round Feistel 3-round Feistel Bernstein–Vazirani
n=5 n=6 n=7 n=8 n=9 n=10 block 6 block 8 n=16
15 18 21 24 27 30 13 17 17
[measurement] [measurement] [measurement] [measurement] [measurement] [measurement] [measurement] [measurement] [measurement]
clean rank-1 (1/31) hybrid (6/63) hybrid (3/127) hybrid (9/255) hybrid (15/511) hybrid (63/1023) clean rank-1 clean rank-1 (2q 219/233) secret in 1 query
✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ —
S4. Disclosure and reproducibility policy Public artifacts (reproducible now): • Interactive browser demo (genuine JS statevector, five attacks): https: //vidraft-quantumos.hf.space/crypto • Quantum-cryptanalysis leaderboard: FINAL-Bench/quantum-bench-leaderboard (Hugging Face). • Companion article (English): https://huggingface.co/blog/FINAL-Bench/ quantum Withheld (pending IP decision): • The hardware-aware circuit-conditioning and readout post-selection technique that enables clean recovery at the reported noise levels and sizes. • Associated engineering heuristics for period readout on noisy hardware. The standard algorithms in Section S2 fully reproduce the Q2-model outcomes. Only the noisescaling method is withheld.
9