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

Anina Köhler 1 , Jakob Murauer 2 , Tim Heine 3 , Stefan Rosemann 4 and Tobias Hemmert 4 · 2026

Read Simon’s Algorithm for the Even-Mansour Cipher on Quantum Hardware by Anina Köhler 1 , Jakob Murauer 2 , Tim Heine 3 , Stefan Rosemann 4 and Tobias Hemmert 4 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25509.txt.

Introduction

Köhler and four colleagues attack Even-Mansour with Simon's algorithm on noisy hardware, as a proof of concept. Simon's algorithm exploits symmetric cipher structure for exponential speedups. While theory is settled, practical NISQ builds remain limited. For N equal to 3 and 4, secret key recovery is shown on ibm_miami. Tests find a scaling limit: DORCIS hit a memory jam at N equal to 5, blocking tuned circuits for larger maps. Results suggest Simon's algorithm works at short lengths, and more scalable tools are needed for larger permutations.

Catalog record

CREATORAnina Köhler 1 , Jakob Murauer 2 , Tim Heine 3 , Stefan Rosemann 4 and Tobias Hemmert 4
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30146
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.25509

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Simon’s Algorithm for the Even-Mansour Cipher on Quantum Hardware Anina Köhler 1 , Jakob Murauer 2 , Tim Heine 3 , Stefan Rosemann 4 and Tobias Hemmert 4 Abstract Simon’s algorithm is a polynomial period-finding algorithm that has been used to exploit the algebraic structure of specific symmetric ciphers, showing that exponential speedups in their cryptanalysis are theoretically possible. While the theoretical framework for an attack using Simon’s algorithm on the Even-Mansour cipher is well-established, practical implementations on noisy intermediate-scale quantum (NISQ) hardware remain limited. This paper presents a proof of concept quantum cryptanalysis of the Even-Mansour cipher using Simon’s period-finding algorithm on NISQ hardware. For N = 3 N=3 and N = 4 N=4 , we successfully demonstrate secret key recovery for N N -bit constructions on the ibm_miami processor. Our experiments also identify a scaling limitation in the classical pre-processing stage: The DORCIS circuit optimization tool encountered a memory bottleneck at N = 5 N=5 , preventing the generation of optimized circuits for larger key lengths. Our results suggest firstly that Simon’s algorithm is effective for the Even-Mansour cipher for short bit lengths on current quantum hardware. Secondly, while DORCIS is effective for the small-scale S-boxes for which it was designed, there remains a need for the investigation of more scalable and efficient synthesis tools capable of handling larger and more general permutations in the context of Even-Mansour ciphers. \scriptstyle N \scriptstyle N \ket{\vec{0}} H^{\otimes N} H^{\otimes N} U_{f} U_{f} H^{\otimes N} H^{\otimes N} A \vec{y}\in\vec{s}^{\bot} \ket{\vec{0}} \vec{x} \vec{x} \vec{y} \vec{y}\oplus f(\vec{x}) Fig. 1: Schema of the 2N -qubit quantum circuit for Simon’s algorithm used to solve the hidden period problem of U_{f} . I Introduction Symmetric cryptography is assumed to be relatively resistant to quantum attacks. Grover’s algorithm [ 12 ] offers a quadratic speedup over classical algorithms for unstructured search problems. It can be applied to any problem where we can efficiently verify a solution. Thus, it can accelerate an exhaustive search for cryptographic keys. It is therefore usually deemed sufficient to double the key length in order to maintain the security of symmetric cryptographic schemes against quantum computers. However: 1. there is often little certainty regarding the underlying computational problems and their complexity, 2. the scaling of quantum resources through hardware and software innovations is constantly advancing, and 3. there is a possibility of (quantum)-algorithmic improvements showing that fewer actual resources are needed. Hence, it remains an important problem to better understand what is computable specifically with quantum resources and to derive appropriate protection measures. Key recovery using quantum period-finding is a well-established approach targeting certain symmetric cryptographic primitives. The idea is to exploit structural properties in a cipher to take advantage of an exponential speedup of quantum over classical algorithms by reducing the problem of finding the key of a cipher to the problem of finding the hidden period of a periodic function—a problem that can be solved efficiently. Simon’s polynomial period-finding algorithm has been utilized to target quantum extensions of symmetric ciphers, thus demonstrating that exponential speedups are theoretically possible [ 16 , 17 , 15 , 22 , 13 ] . However, the approach requires the attacker to query an encryption oracle about quantum states, which means that the encryption function (involving the secret key) is used inside a quantum algorithm. While this is a common attack model in quantum cryptanalysis [ 2 , 15 , 1 ] , the attack is considered impractical. To reduce the number of superposition queries and extend the application to related symmetric constructions, combinations of Simon’s algorithm with Grover’s algorithm have been proposed. The idea is to still leverage periodicity to find the secret key, but instead of directly defining a periodic function, to define a family of functions, one of which is periodic. Grover’s algorithm is used to search through the family of functions and Simon’s algorithm internally identifies the periodic one, essentially offering a tradeoff between the size of the Grover search space and the number of classical queries and superposition queries. The Grover-meets-Simon algorithm uses superposition queries and has been applied to target the ciphers DESX, PRINCE and PRIDE [ 18 ] . The Offline Simon’s algorithm has been utilized to target the symmetric block ciphers FX and Even-Mansour [ 3 ] , Chaskey, PRINCE, Elephant [ 4 ] , and 2XOR [ 5 ] in a weaker attack model where the attacker is limited to classical queries to an encryption oracle. In particular, the application of the Offline Simon’s algorithm to 2XOR for the first time proved a more than quadratic (2.5) speedup compared to a symmetric cipher’s best classical attack using only classical queries. The attacks also reveal that common key length extension techniques can be less effective in a quantum setting. Using substitution boxes (S-boxes) that we constructed in a similar way to the S-box used in the AES algorithm, we implement a proof of concept of the attack on the minimal symmetric Even-Mansour (EM) cipher using Simon’s algorithm [ 17 ] on quantum hardware. Since EM is underlying many block cipher constructions, including 1-round AES, and the application of Simon’s algorithm is the core idea in all related attacks, we believe that a practical evaluation of concrete examples on current hardware usefully illustrates the concept and can offer valuable insights. II Key Recovery for the Even-Mansour Cipher using Simon’s Algorithm II-A Simon’s Algorithm Let f:\{0,1\}^{N}\rightarrow\{0,1\}^{N} be a function on binary strings that is two-to-one. Suppose further that there is a N -bit string \vec{s} such that for all \vec{x}\neq\vec{y} , the equality f(\vec{x})=f(\vec{y}) holds if and only if \vec{y}=\vec{x}\oplus\vec{s} , where \oplus is the bitwise exclusive or. This property is called Simon’s promise . Simon’s problem asks to find that hidden period \vec{s} of f . If f can be evaluated in superposition using the query gate \displaystyle U_{f}(\ket{\vec{x}}\ket{\vec{a}})=\ket{\vec{x}}\ket{\vec{a}\oplus f(\vec{x})}, then due to interference on the collisions of f , Simon’s algorithm [ 23 , 24 ] can be used to sample N-1 linearly independent vectors orthogonal to \vec{s} uniformly at random. These vectors can be used to obtain \vec{s} in \mathcal{O}(N) in terms of query complexity. This is providing an exponential advantage over classical query algorithms since the best classical strategy is to randomly query f until a collision has been found. Any classical solution therefore necessarily has a worst case runtime that is exponential in N [ 24 ] . For \vec{v}\in\{0,1\}^{N} , let \displaystyle\vec{v}^{\bot}=(\spn\{\vec{v}\})^{\bot}=\{\vec{y}\in\{0,1\}^{N}:\vec{y}\cdot\vec{v}=0\} denote the orthogonal complement of the subspace spanned by \vec{v} in \{0,1\}^{N} . The key idea of Simon’s algorithm is to notice that H^{\otimes N}(\ket{\vec{x}}+\ket{\vec{x}\oplus\vec{v}}) , which is the Hadamard transform applied to a superposition of two states \ket{\vec{x}} and \ket{\vec{x}\oplus\vec{v}} that have the same amplitude and differ by \vec{v} , gives \displaystyle\frac{1}{2^{N}}\sum_{\vec{y}\in\vec{v}^{\bot}}((-1)^{\vec{x}\cdot\vec{y}}+(-1)^{(\vec{x}\oplus\vec{v})\cdot\vec{y}})\ket{\vec{y}}, which is a superposition of states that are orthogonal to \vec{v} . This observation is useful because by measuring this state, a vector \vec{y}\in\vec{v}^{\bot} is obtained. By creating interference on the collisions of f , Simon’s algorithm uses this result to sample vectors orthogonal to \vec{s} uniformly at random. The schema of the quantum circuit for Simon’s algorithm is illustrated in Fig. 1 : (1) The input and output registers are prepared in the all zero state. (2) A

Read the complete text