Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Simon’s Algorithm and Symmetric Crypto: Generalizations and Automatized Applications

Federico Canale, Gregor Leander, Lukas Stennes

Published Jan 1, 2022• 21 citations
Publisher
DOI
10.1007/978-3-031-15982-4_26

Related papers

Breaking symmetric cryptosystems using the offline distributed Grover-meets-Simon algorithm

Bao-Min Zhou, Zheng Yuan

Quantum Information Processing•Sep 2, 2023•7 citations

Public-Key Crypto-systems Using Symmetric-Key Crypto-algorithms

Bruce Christianson, Bruno Crispo, James A. Malcolm

Lecture notes in computer science•Jan 1, 2001•2 citations

Quantum Related-Key Attack Based on Simon’s Algorithm and Its Applications

Ping Zhang

With the development of quantum technology, quantum computing has an increasingly significant impact on cryptanalysis. Several quantum algorithms, such as Simon’s algorithm, Grover’s algorithm, the Bernstein–Vazirani algorithm, Shor’s algorithm, and the Grover-meets-Simon algorithm, have been proposed successively. However, almost all cryptanalysis is based on the quantum chosen-plaintext attack (qCPA) model. This paper focuses on a powerful cryptanalytic model, quantum related-key attack (qRKA), and proposes a strategy of qRKAs against symmetric ciphers using Simon’s algorithm. We construct a periodic function to efficiently recover the secret key of symmetric ciphers if the attacked symmetric ciphers satisfy Simon’s promise, and present the complexity analysis on specific symmetric ciphers. Then, we apply qRKA to the Even–Mansour cipher and SoEM construction, recover their secret keys, and show their complexity comparison in the distinct attack models. This work is of great significance for the qRKA cryptanalysis of existing provably secure cryptographic schemes and the design of future quantum secure cryptographic schemes.

Symmetry•Apr 24, 2023•6 citations

Exact distributed quantum algorithm for generalized Simon’s problem

Hao Li, Daowen Qiu, Le Luo +1 more

Abstract Simon’s problem is one of the most important problems demonstrating the power of quantum algorithms, as it greatly inspired the proposal of Shor’s algorithm. The generalized Simon’s problem is a natural extension of Simon’s problem, and also a special hidden subgroup problem: Given a function f : {0, 1} n → {0, 1} m , with the property that for any x, y ∈ {0, 1} n , there is some unknown hidden subgroup S ≤ Z n 2 such that f (x) = f (y) iff x ⊕ y ∈ S, where |S| = 2 k for some 0 ≤ k ≤ n (m ≥ n − k). The goal of generalized Simon’s problem is to find the hidden subgroup S. In this paper, we present two key contributions. Firstly, we characterize the structure of the generalized Simon’s problem in distributed scenario and introduce a corresponding distributed quantum algorithm. Secondly, we refine the algorithm to ensure exactness due to the application of quantum amplitude amplification technique. Our algorithm offers exponential acceleration compared to the distributed classical algorithm. When contrasted with the centralized quantum algorithm for the generalized Simon’s problem, our algorithm’s oracle requires fewer qubits, thus making it easier to be physically implemented. Particulary, the exact distributed quantum algorithm we develop for the generalized Simon’s problem outperforms the best previously proposed distributed quantum algorithm for Simon’s problem in terms of generalizability and exactness.

arXiv:2307.14315•Acta Informatica•Mar 10, 2024•21 citations

Post Quantum Cryptography Algorithms: A Review and Applications

Bikram Paul, Gaurav Trivedi

Lecture notes in networks and systems•Jan 1, 2023•10 citations

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

Anina Köhler, Jakob Murauer, Tim Heine +2 more

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 and N = 4, we successfully demonstrate secret key recovery for 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, 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.

quant-pharXiv:2604.25509•Apr 29, 2026•1 citation
With the development of quantum technology, quantum computing has an increasingly significant impact on cryptanalysis. Several quantum algorithms, such as Simon’s algorithm, Grover’s algorithm, the Bernstein–Vazirani algorithm, Shor’s algorithm, and the Grover-meets-Simon algorithm, have been proposed successively. However, almost all cryptanalysis is based on the quantum chosen-plaintext attack (qCPA) model. This paper focuses on a powerful cryptanalytic model, quantum related-key attack (qRKA), and proposes a strategy of qRKAs against symmetric ciphers using Simon’s algorithm. We construct a periodic function to efficiently recover the secret key of symmetric ciphers if the attacked symmetric ciphers satisfy Simon’s promise, and present the complexity analysis on specific symmetric ciphers. Then, we apply qRKA to the Even–Mansour cipher and SoEM construction, recover their secret keys, and show their complexity comparison in the distinct attack models. This work is of great significance for the qRKA cryptanalysis of existing provably secure cryptographic schemes and the design of future quantum secure cryptographic schemes.
Abstract Simon’s problem is one of the most important problems demonstrating the power of quantum algorithms, as it greatly inspired the proposal of Shor’s algorithm. The generalized Simon’s problem is a natural extension of Simon’s problem, and also a special hidden subgroup problem: Given a function f : {0, 1} n → {0, 1} m , with the property that for any x, y ∈ {0, 1} n , there is some unknown hidden subgroup S ≤ Z n 2 such that f (x) = f (y) iff x ⊕ y ∈ S, where |S| = 2 k for some 0 ≤ k ≤ n (m ≥ n − k). The goal of generalized Simon’s problem is to find the hidden subgroup S. In this paper, we present two key contributions. Firstly, we characterize the structure of the generalized Simon’s problem in distributed scenario and introduce a corresponding distributed quantum algorithm. Secondly, we refine the algorithm to ensure exactness due to the application of quantum amplitude amplification technique. Our algorithm offers exponential acceleration compared to the distributed classical algorithm. When contrasted with the centralized quantum algorithm for the generalized Simon’s problem, our algorithm’s oracle requires fewer qubits, thus making it easier to be physically implemented. Particulary, the exact distributed quantum algorithm we develop for the generalized Simon’s problem outperforms the best previously proposed distributed quantum algorithm for Simon’s problem in terms of generalizability and exactness.
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 and N = 4, we successfully demonstrate secret key recovery for 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, 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.