Simon's Algorithm for the Even-Mansour Cipher on Quantum Hardware

This paper presents a proof-of-concept quantum cryptanalysis of the Even-Mansour cipher using Simon's algorithm on NISQ hardware, successfully recovering secret keys for 3-bit and 4-bit constructions on the ibm_miami processor while highlighting memory bottlenecks in current circuit optimization tools for larger key lengths.

The Gist

Imagine you are trying to crack a safe that uses a very specific, tricky lock. This paper is about a team of researchers who tried to pick that lock using a new kind of "super-tool" called a quantum computer. They didn't just guess the combination; they used a clever mathematical trick to find the pattern hidden inside the lock.

Here is the breakdown of their experiment in simple terms:

The Lock: The Even-Mansour Cipher

Think of the Even-Mansour cipher as a simple but sturdy safe. It works like this:

1. You put a message (the plaintext) into the safe.
2. You mix it with a secret key (Key 1).
3. You run it through a public, chaotic machine (a permutation) that scrambles it up.
4. You mix it again with a second secret key (Key 2).
5. The result is the locked message.

The goal of the attackers (the researchers) was to figure out what those two secret keys were.

The Super-Tool: Simon's Algorithm

Normally, if you wanted to find a secret key, you might have to try billions of combinations one by one. That's like trying every single key on a giant keyring until one fits.

But the researchers used Simon's Algorithm. Imagine this algorithm as a magical detective that doesn't look for the key directly. Instead, it looks for a hidden rhythm or a pattern.

• The researchers set up a special scenario where the lock behaves in a weird way: if you turn the dial a certain amount (the secret key), the lock ends up in the exact same position as if you hadn't turned it at all.
• Simon's Algorithm is great at finding these "hidden rhythms" (periods) much faster than a normal computer could. It's like listening to a song and instantly knowing the beat, whereas a normal computer has to count every single drum hit.

The Experiment: Building the Lock on a Quantum Computer

The researchers wanted to see if this magical detective could actually work on real, physical hardware. They built a tiny version of the lock on a quantum computer called IBM Miami.

1. The Blueprint (S-boxes): To make the lock work, they needed a "scrambler" (called an S-box). They built these scramblers using logic similar to the ones used in the famous AES encryption standard, but much smaller (for 3-bit and 4-bit keys).
2. The Translation Problem: Quantum computers speak a different language than regular computers. The researchers had to translate their classical "scrambler" designs into a language the quantum computer could understand. They used a tool called DORCIS to do this translation.
   • The Bottleneck: This tool worked great for the tiny 3-bit and 4-bit locks. However, when they tried to translate a slightly larger 5-bit lock, the tool ran out of memory. It was like trying to fold a massive map into a tiny pocket; the paper just wouldn't fit. This stopped them from testing bigger keys.
3. The Noise: Quantum computers are currently very sensitive, like a house of cards in a windstorm. To keep the experiment steady, the researchers used special techniques (like "Dynamical Decoupling") to calm the qubits down, similar to how you might hold a camera steady to take a clear photo in the wind.

The Results

They ran the experiment on two small locks: one with a 3-bit key and one with a 4-bit key.

• Success: In both cases, the quantum computer successfully found the hidden rhythm. From that rhythm, the researchers calculated the secret keys.
• Reproducibility: They ran the test five times for each lock size, and it worked every time.
• The Limitation: As mentioned, they couldn't test a 5-bit lock because the translation tool (DORCIS) crashed due to memory limits.

The Takeaway

The paper concludes two main things:

1. It Works (for now): Simon's Algorithm is a real, working method to break this specific type of encryption on current quantum hardware, but only for very small keys. It proves that quantum computers can theoretically find these hidden patterns exponentially faster than classical computers.
2. The Tools Need an Upgrade: While the quantum computer did its job, the software used to prepare the "blueprints" for the quantum computer hit a wall. To break larger, more realistic locks in the future, we need better tools to translate these designs into quantum circuits without running out of memory.

In short: They proved the concept works on a small scale, but the "construction crew" (the software tools) needs to get stronger before they can build the big skyscrapers.

Technical Summary

1. Problem Statement

The paper addresses the practical feasibility of executing quantum cryptanalysis attacks on symmetric ciphers using current Noisy Intermediate-Scale Quantum (NISQ) hardware. Specifically, it targets the Even-Mansour (EM) cipher, a minimal block cipher construction based on a public permutation and two secret keys.

While the theoretical framework for breaking the EM cipher using Simon's Algorithm is well-established (offering an exponential speedup over classical attacks by finding a hidden period), practical implementation has been limited. The core challenges include:

• Hardware Constraints: NISQ devices suffer from noise, decoherence, and limited qubit connectivity, making deep circuits (required for complex permutations) difficult to execute.
• Circuit Synthesis Bottlenecks: Converting classical cryptographic permutations (S-boxes) into optimized, reversible quantum circuits is computationally expensive. Existing tools often fail to scale to larger key lengths due to memory constraints.
• Oracle Implementation: The attack requires implementing the encryption function as a quantum oracle, which involves synthesizing non-linear permutations into quantum gates.

2. Methodology

The authors implemented a proof-of-concept attack on the IBM ibm_miami processor. The methodology involved three main stages:

A. Cryptographic Construction

• Cipher: The Even-Mansour scheme $EM_{k_1, k_2}(x) = P(x \oplus k_1) \oplus k_2$, where $P$ is a public permutation and $k_1, k_2$ are secret keys.
• Permutation ($P$): For $N=3$ and $N=4$, the authors constructed bijective maps inspired by the AES S-box. These were defined as inversion in the finite field $F_{2^N}$ followed by an affine transformation.
• Attack Vector: The attack defines a function $f(x) = EM(x) \oplus P(x)$. This function has a hidden period $k_1$. Simon's algorithm is used to find $k_1$, after which $k_2$ is recovered classically or via a simple quantum query.

B. Quantum Circuit Synthesis (DORCIS)

• Toolchain: The authors used the DORCIS (Depth Optimized Quantum Implementation of Substitution Boxes) tool to synthesize the classical permutation tables into reversible quantum circuits.
• Optimization: DORCIS decomposes permutations into elementary gates (Pauli-X, Toffoli/CCNOT, SWAP) and minimizes circuit depth.
• Scaling Limit: The tool successfully generated circuits for $N=3$ and $N=4$ but failed for $N=5$ due to a memory bottleneck on a high-performance CPU (3.9 TiB RAM), preventing the generation of circuits for larger instances.

C. Hardware Execution and Error Mitigation

To execute the attack on the noisy ibm_miami processor, the team employed specific mitigation strategies:

• Qubit Mapping: They manually mapped logical qubits to specific physical qubit subgraphs ($[0, 1, 2, 12, 11, 10]$ for $N=3$ and $[0, 1, 2, 3, 13, 12, 11, 10]$ for $N=4$) to utilize the lattice topology and avoid automatic routing overhead.
• Dynamical Decoupling (DD): Applied symmetric sequences of unitaries (e.g., alternating X pulses) on idle qubits to suppress low-frequency environmental noise and crosstalk.
• Pauli Twirling: Randomly inserted logically equivalent Pauli operator pairs before and after gates to convert coherent errors into stochastic Pauli errors, preventing systematic phase distortions that could obscure the algorithm's structural collisions.

3. Key Contributions

1. First Practical Demonstration: This is a successful proof-of-concept demonstrating secret key recovery for the Even-Mansour cipher on actual quantum hardware ($N=3$ and $N=4$).
2. Error Mitigation Validation: The paper validates that combining Dynamical Decoupling and Pauli Twirling allows Simon's algorithm to function effectively despite the deep circuit depths and noise inherent in NISQ devices.
3. Identification of Classical Bottlenecks: The study highlights that the limiting factor for scaling these attacks is currently the classical pre-processing (circuit synthesis) rather than the quantum hardware itself. The DORCIS tool failed at $N=5$ due to memory constraints.
4. Empirical Data: The authors provide detailed statistical distributions of measurement outcomes, showing that the experimental results align with theoretical predictions when noise is accounted for.

4. Results

• 3-bit Case ($N=3$):
  • Successfully recovered the secret key $k_1 = (0, 1, 0)$ and $k_2 = (1, 1, 0)$.
  • The circuit depth was 23 (T-depth 3).
  • After 5 independent experiments (105 shots each), the measurement distribution clearly peaked at the vectors orthogonal to the true period, allowing successful linear algebra recovery of the key.
• 4-bit Case ($N=4$):
  • Successfully recovered $k_1 = (0, 1, 0, 1)$ and $k_2 = (1, 1, 0, 1)$.
  • The circuit depth increased to 54 (T-depth 7).
  • Despite the increased depth and noise, the distribution of results remained distinct enough to solve the system of linear equations for the key.
• Error Analysis:
  • The authors modeled the noise as a depolarizing channel. They estimated a noise parameter $p \approx 0.434$ based on gate error rates and total pulse count.
  • The experimental data matched the theoretical noisy distribution, confirming that the deviations were due to hardware noise rather than algorithmic failure.
• Scaling Failure: The DORCIS tool could not generate a circuit for $N=5$, indicating that current classical synthesis tools are not yet scalable for larger key lengths.

5. Significance

• Theoretical Validation: The results confirm that the theoretical exponential speedup of Simon's algorithm is achievable in practice for symmetric ciphers, provided the key length is small enough for current hardware.
• Security Implications: It reinforces the vulnerability of symmetric constructions like Even-Mansour (and by extension, 1-round AES) to quantum attacks if an encryption oracle is accessible in superposition.
• Hardware vs. Software Bottleneck: The paper shifts the focus of the challenge from "can we run the quantum algorithm?" to "can we synthesize the circuit?" It suggests that future progress in quantum cryptanalysis depends heavily on developing more scalable classical synthesis tools (potentially using machine learning or heuristics) rather than just waiting for better qubits.
• NISQ Viability: It demonstrates that with sophisticated error mitigation and manual qubit mapping, complex cryptanalytic algorithms can yield correct results on current, noisy hardware.