💻 computer science

Quantum Cryptanalysis on IBM Quantum Hardware: Extending Even--Mansour Period Recovery from $N=4$ to $N=10$

This paper presents a genuine, uncompiled demonstration on real IBM quantum hardware of textbook-faithful quantum cryptanalysis using Simon's algorithm to recover hidden periods for Even-Mansour and Feistel cipher structures up to record sizes (N=10), while providing a comprehensive benchmark of five attacks across four symmetric-cipher paradigms with explicit caveats regarding their scope, error mitigation reliance, and lack of threat to full-scale modern encryption.

Original authors: Taebong Kim, Youngsik Hong, Minsik Kim, Sunyoung Choi, Jaewon Jang, Junghoon Shin, Minseo Kim

Published 2026-07-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Taebong Kim, Youngsik Hong, Minsik Kim, Sunyoung Choi, Jaewon Jang, Junghoon Shin, Minseo Kim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where secret codes aren't just locked in a vault, but hidden inside a maze that only a ghost can walk through. This is the realm of quantum cryptanalysis, a branch of science where researchers use the strange, spooky rules of quantum physics to test how strong our digital locks really are. To understand this, you need to know three simple things. First, "symmetric ciphers" are like a single key that locks and unlocks a treasure chest; if you have the key, you can open it, but if you don't, you're stuck. Second, "quantum computers" are special machines that can try many paths in a maze at the same time, unlike normal computers that must try one path, then another, then another. Finally, there's a famous trick called "Simon's algorithm," which is like a super-smart detective that can find a hidden pattern in a chaotic mess much faster than a regular detective, but only if the mess has a very specific, repeating structure.

Why does anyone care? Because if a quantum computer can find these patterns easily, the secret keys protecting our bank accounts, messages, and national secrets could be cracked. But here's the catch: building a quantum computer that is big enough and quiet enough to actually do this is incredibly hard. They are currently very noisy, like trying to hear a whisper in a rock concert. This paper is about a team of researchers who tried to teach a real, noisy quantum computer to find these hidden patterns in secret codes, pushing the limits of what is currently possible in the real world.

The Paper: A Quantum Detective on a Noisy Stage

The researchers, working with a real quantum computer made by IBM (specifically the "ibm_kingston" chip), decided to play a game of "find the hidden pattern." They focused on a specific type of secret code structure called the Even-Mansour cipher. Imagine this cipher as a machine that takes a secret number (the key) and scrambles a message. The goal of the attack is to find the "period"—a hidden repeating rhythm in how the machine scrambles the data. If you find the rhythm, you can figure out the secret key.

In the past, scientists had only managed to do this on real hardware for very tiny, simple versions of the code (where the secret number was just 4 bits long). This team wanted to see how far they could push the real machine. They managed to successfully find the hidden rhythm for a version where the secret number was 10 bits long. That might not sound like a lot to you, but in the world of quantum hardware, jumping from 4 to 10 is a massive leap. It's like going from balancing on one foot to running a marathon on a tightrope.

They didn't stop there. They also tested their detective skills on other types of code structures:

The 3-Round Feistel: A structure used in older codes (like the famous DES). They successfully found the hidden rhythm for block sizes of 6 and 8.
Bernstein-Vazirani: A simpler linear puzzle. They found a 16-bit secret in just one single question (query), which is exactly what the math promised.
Grover's Search: They tested a method for searching unstructured keys, showing that the quantum computer could find a key in about 13 steps when a normal computer would need 256 steps.

The Reality Check: How Good Was It?

Here is the most important part of the story, and the part where the authors are very, very honest. While they found the patterns, they didn't break the code in a way that would let them steal your bank account today.

For the larger puzzles (where the secret was 6 bits or more), the quantum computer got a bit "noisy" and confused. It didn't point to the one correct answer immediately. Instead, it gave a list of the top candidates. The researchers then used a regular computer to check the top 16, 32, 64, or 128 candidates from the quantum list. The true secret key was usually found very high up on that list (often within the top 63 candidates), which is much better than guessing randomly.

The authors are very clear: This is not a "quantum advantage" yet.

No Magic Bullet: They did not break the full, real-world versions of famous codes like AES or RSA. They only broke simplified, reduced versions of the structures.
No Super-Speed: For the larger puzzles, the quantum computer didn't solve the whole thing alone. It narrowed down the list of suspects, but a regular computer still had to do the final work. The speedup they saw was in the number of questions asked, not in the total time it took to crack the code.
Noise vs. Perfection: They used "error mitigation" (a fancy way of saying they cleaned up the noisy data) rather than "error correction" (which would fix the errors perfectly). This means their results are impressive for today's technology, but they are not the final, perfect solution.

The Big Picture

The team also ran a massive simulation on a supercomputer to see how far this could go if they had perfect, noise-free machines. They found that while a quantum computer could theoretically handle these puzzles easily, a normal computer would run out of memory trying to simulate a quantum computer with just 25 qubits (the basic units of quantum information). A slightly larger puzzle would require 4.5 petabytes of memory—more than most data centers have!

So, what is the takeaway? This paper is a "world record" for how big a secret code structure a real, noisy quantum computer has successfully analyzed. It proves that the math works on real hardware, even if the hardware is still a bit shaky. It's a proof of concept that says, "We can do this, but we need better, quieter machines before we can actually break the real world's secrets." The authors have made their code and data public so anyone can check their work, ensuring that this isn't just a claim, but a reproducible step forward in the race between quantum computers and secret codes.

Technical Summary: Quantum Cryptanalysis on IBM Quantum Hardware

Problem Statement

Theoretical research has long established that specific symmetric-cipher structures, such as the Even–Mansour cipher and 3-round Feistel networks, can be reduced to hidden-period problems solvable by Simon's algorithm. However, a significant gap exists between these theoretical reductions and practical execution on noisy intermediate-scale quantum (NISQ) devices. Prior to this work, real-hardware demonstrations of such key recovery were limited to very small security parameters (specifically $N=4$ ) due to device noise and the lack of fault-tolerant error correction. The challenge lies in extending these attacks to larger structure sizes ( $N > 4$ ) on real hardware while maintaining "genuine" algorithmic integrity—meaning the circuits must implement the actual keyed maps without transpilation shortcuts that would trivialize the search.

Methodology

The authors executed "genuine-un-compiled, textbook-faithful" quantum cryptanalysis on the IBM ibm_kingston processor (Heron generation) using the Qiskit framework. The methodology is characterized by the following components:

Algorithmic Scope: The study targets four symmetric-cipher design paradigms:
1. Linear Structure: Bernstein–Vazirani algorithm (single query).
2. Unstructured Search: Grover's algorithm applied to a reduced SPN (Substitution-Permutation Network) key search.
3. Hidden-Period Problems: Simon's algorithm applied to:
  - Even–Mansour cipher.
  - CBC-MAC forgery.
  - 3-round Feistel (DES-family) construction.
Execution Strategy:
- Real Hardware: Experiments utilized a comprehensive readout error-mitigation stack (including calibration, dynamical decoupling, and twirling) rather than fault-tolerant error correction.
- Hybrid Approach for $N > 5$ : For Even–Mansour instances where the noise prevented a clean "rank-1" recovery, the authors employed a quantum-narrowing + classical-verification hybrid. The quantum circuit generated a shortlist of top-ranked candidates (e.g., top-16 or top-128), which were then verified classically.
- Validation: All hardware results were cross-validated against independent control keys to ensure recovered periods were not artifacts of specific key selections.
- Simulation: A breadth-first benchmark was conducted using genuine statevector simulation (on NVIDIA B200 hardware) up to the classical memory ceiling of 25 qubits to validate the un-compiled circuits.

Key Results

1. Extension of Real-Hardware Frontier

The paper reports the recovery of the Even–Mansour hidden period up to security parameter $N = 10$ on real hardware.

$N = 5$ : Achieved a clean, rank-1 recovery (differential Simon) where the true key was the top candidate.
$N = 6$ to $N = 10$ : Achieved via the hybrid approach. While the true key was not always the single top output due to noise, its rank tracked the birthday bound ( $2^{n/2}$ ), remaining orders of magnitude below the random expectation ( $2^{n-1}$ ).
Comparison: This exceeds the largest previously reported real-hardware size of $N = 4$ .

2. Feistel and Linear Structure Recovery

3-Round Feistel: Cleanly recovered the period for block sizes 6 and 8 (rank-1, exact) on real hardware. A 21-qubit block-10 instance was verified in simulation and submitted to hardware.
Bernstein–Vazirani: Successfully extracted a 16-bit linear secret in a single query on real hardware.

3. Complexity Separation

The study demonstrates the theoretical query-complexity separation:

Simon-based attacks: Exponential classical query complexity ( $2^{n/2}$ ) vs. polynomial quantum queries ( $\Theta(n)$ ).
Grover-based attacks: Quadratic speedup (e.g., recovering an 8-bit key in $\approx 13$ iterations vs. 256 classical evaluations).

Significance and Claims

The authors explicitly frame their contributions with a focus on honesty and reproducibility, avoiding overstatement of "quantum advantage."

Real-Hardware Demonstration: The primary contribution is the demonstration of genuine quantum cryptanalysis on real hardware at record structure sizes ( $N=10$ for Even–Mansour), bridging the gap between theoretical reductions and physical execution.
Breadth of Coverage: The work provides a comprehensive benchmark across four distinct cryptographic paradigms (Linear, Unstructured, Hidden-Period) and five specific attacks, all validated to the classical simulation ceiling.
No End-to-End Quantum Advantage: The paper explicitly states that these attacks do not constitute a quantum advantage over classical methods in terms of end-to-end cost. The attacks asymptotically follow the birthday bound, meaning classical collision-finding achieves comparable scaling. The separation is strictly in query complexity for the distinguisher, not total computational cost.
Scope Limitations:
- The attacks target reduced or structured constructions (Even–Mansour, 3-round Feistel, reduced SPN), not full AES, RSA, or 16-round DES.
- The results rely on error mitigation, not fault-tolerant error correction.
- The Q2 (quantum-query) oracle model is assumed, though the authors acknowledge its practical limitations and note that offline-Simon reductions can relax some assumptions to Q1.

In summary, this paper serves as a rigorous, reproducible benchmark of genuine quantum algorithms on NISQ hardware, demonstrating that while current devices cannot break modern full-scale ciphers, they can successfully execute complex cryptanalytic reductions on structured primitives at sizes previously unattainable on real hardware.