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• 18 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•6 citations

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

Bruce Christianson, Bruno Crispo A, 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

3. Algorithmes quantiques pour la cryptographie

Pierre-Alain Fouque, Pascal Lafourcade, Ludovic Perret

Cairn.info•Jan 1, 2026•0 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•18 citations

Threats to Modern Cryptography: Grover’s Algorithm

Mina Mina-Zicu, Emil Simion

•Sep 27, 2020•5 citations
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.