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

China Communications

General method of combining Grover and Simon for attacking block ciphers

Xiang-Qun Fu, Bao Wansu, Shi Jianhong, Li Tan

Published Apr 9, 2024• 1 citation
Publisher

Abstract

The compatibility of different quantum algorithms should be considered when these algorithms are combined. In this paper, the method of combining Grover and Simon is studied for the first time, under some preconditions or assumptions. First, we give two preconditions of applying Grover's algorithm, which ensure that the success probability of finding the marked element is close to 1. Then, based on these two preconditions, it is found out that the success probability of the quantum algorithm for FX-construction is far less than 1. Furthermore, we give the design method of the Oracle function, and then present the general method of combining Grover and Simon algorithm for attacking block ciphers, with success probability close to 1.

DOI
10.23919/jcc.ea.2021-0508.202401

Related papers

Tight Analysis of Grover-Meets-Simon and Alg-PolyQ2 Attacks via Formalizing Quantum Rank-Solving under Deferred Measurement

Qiqing Xia, Qianru Zhu, Huiqin Xie +1 more

Abstract The combination of quantum algorithms is one promising approach to attacking symmetric cryptography. In this paper, we study in detail the Grover-meets-Simon and Alg-PolyQ2 algorithms under deferred measurement, which combine the ideas of Grover’s and Simon’s algorithms and are applicable to attacking the FX construction. By converting intermediate measurements into unitary operations deferred to the end of the quantum circuit, both quantum algorithms involve a quantum rank-solving problem. To address it, we first provide a formal analysis of the generalized quantum Gauss–Jordan elimination and characterize the resulting quantum state after the corresponding unitary operations, which serves as a subroutine in these two algorithms. Subsequently, we derive the tight bounds of the attack success probability of these two algorithms based on the initial amplitude, offering a novel perspective that confirms their effectiveness. Furthermore, our research perspective provides an idea for analyzing the attack success probability for some quantum algorithms integrating Grover’s algorithm without considering quantum input length, and contributes to a deeper understanding of these attacks’ underlying mechanisms under the deferred measurement principle.

Quantum Information and Computation•Dec 1, 2025•0 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

Quantum Attacks without Superposition Queries: the Offline Bernstein-Vazirani Meets Grover Algorithm

Bao-Min Zhou, Zheng Yuan

Block cryptanalysis has a major breakthrough in the model of superposition queries. For instance, Simon’s algorithm can efficiently break various constructions. In practice, Bernstein-Vaziran’s algorithm can also realize the periodic search of the vector function. Moreover, in some cases, it can have more advantages than the Simon’s algorithm.In the context of this study, we present an algorithm that combines Grover’s and Bernstein-Vazirani’s quantum algorithms. This algorithm empowers us to carry out key recovery attacks on Feistel structures. on Feistel structures, FX construction and Even Mansour construction. We exploit cryptosystems’ algebraic structure to launch successful key recovery attacks, considering that quantum attackers can only make classical queries. Through comparison, it can be concluded that this algorithm has stronger practicability in attacking block ciphers.

International Conference on Computing, Communication, Perception and Quantum Technology (CCPQT)•Aug 4, 2023•1 citation

A Summary of the Security of Tweakable Block Ciphers Against Simon's Quantum Algorithm

Jianfeng Ruan, Gang Liu, Bing Shen +1 more

Tweakable block ciphers are more flexible than traditional block ciphers and widely used in modes of operation such as MAC and authenticated encryption. With the development of quantum computing, the threat of quantum algorithms to the security of cryptosystems is increasing. Research shows that some classical secure symmetric cryptographic constructions or schemes become vulnerable to the quantum attacks based on Simon's algorithm. This paper studies the security of tweakable block cipher constructions under quantum attacks based on Simon's algorithm, summarizes the quantum attack methods of Simon's algorithm and quantum-resistant constructions, and provides methods to enhance the quantum security of tweakable block ciphers.

International Conference on Cloud Computing and Big Data Analytics (ICCCBDA)•Apr 24, 2025•0 citations

Quantum Attack Implementation of TWINE Block Cipher

Zou Kun, Xinfeng Dong, Zhang Fuzhong +1 more

The result of resource consumption in quantum attack implementation of cryptographic algorithm is an important metric to evaluate the security strength of cryptographic algorithm against quantum attack. This paper studies complete implementation of quantum attack on cryptographic algorithm using Grover meets Simon method. We find 9-round quantum distinguisher whose round is the longest currently about TWINE, and utilize Grover meets Simon method to carry out 14/15-round quantum key recovery attack on TWINE-80/TWINE-128 with lower complexity than exhaust attack. Furthermore, we give complete implementation of quantum oracle and QAA algorithm in TWINE’s quantum key recovery attack for the first time. The circuit is suitable for all implementation of quantum key recovery attack on block cipher using Grover meets Simon method.

Asia Conference on Algorithms, Computing and Machine Learning (CACML)•Mar 28, 2025•0 citations

Feasibility Analysis of Grover-meets-Simon Algorithm

Qianru Zhu, Huiqin Xie, Qiqing Xia +1 more

Quantum algorithm is a key tool for cryptanalysis. At present, people are committed to building powerful quantum algorithms and tapping the potential of quantum algorithms, so as to further analyze the security of cryptographic algorithms under quantum computing. Recombining classical quantum algorithms is one of the current ideas to construct quantum algorithms. However, they cannot be easily combined, the feasibility of quantum algorithms needs further analysis in quantum environment. This paper reanalyzes the existing combined algorithm Grover-meets-Simon algorithm in terms of the principle of deferred measurement. First of all, due to the collapse problem caused by the measurement, we negate the measurement process of Simon's algorithm during the process of the Grover-meets-Simon algorithm. Second, since the output of the unmeasured Simon algorithm is quantum linear systems of equations, we discuss the solution of quantum linear systems of equations and find it feasible to consider the deferred measurement of the parallel Simon algorithm alone. Finally, since the Grover-meets-Simon algorithm involves an iterative problem, we reconsider the feasibility of the algorithm when placing multiple measurements at the end. According to the maximum probability of success and query times, we get that the Grover-meets-Simon algorithm is not an effective attack algorithm when putting the measurement process of the Simon algorithm in the iterative process at the end of Grover-meets-Simon algorithm.

arXiv:2301.06706•Jan 17, 2023•0 citations
The compatibility of different quantum algorithms should be considered when these algorithms are combined. In this paper, the method of combining Grover and Simon is studied for the first time, under some preconditions or assumptions. First, we give two preconditions of applying Grover's algorithm, which ensure that the success probability of finding the marked element is close to 1. Then, based on these two preconditions, it is found out that the success probability of the quantum algorithm for FX-construction is far less than 1. Furthermore, we give the design method of the Oracle function, and then present the general method of combining Grover and Simon algorithm for attacking block ciphers, with success probability close to 1.
Abstract The combination of quantum algorithms is one promising approach to attacking symmetric cryptography. In this paper, we study in detail the Grover-meets-Simon and Alg-PolyQ2 algorithms under deferred measurement, which combine the ideas of Grover’s and Simon’s algorithms and are applicable to attacking the FX construction. By converting intermediate measurements into unitary operations deferred to the end of the quantum circuit, both quantum algorithms involve a quantum rank-solving problem. To address it, we first provide a formal analysis of the generalized quantum Gauss–Jordan elimination and characterize the resulting quantum state after the corresponding unitary operations, which serves as a subroutine in these two algorithms. Subsequently, we derive the tight bounds of the attack success probability of these two algorithms based on the initial amplitude, offering a novel perspective that confirms their effectiveness. Furthermore, our research perspective provides an idea for analyzing the attack success probability for some quantum algorithms integrating Grover’s algorithm without considering quantum input length, and contributes to a deeper understanding of these attacks’ underlying mechanisms under the deferred measurement principle.
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.
Block cryptanalysis has a major breakthrough in the model of superposition queries. For instance, Simon’s algorithm can efficiently break various constructions. In practice, Bernstein-Vaziran’s algorithm can also realize the periodic search of the vector function. Moreover, in some cases, it can have more advantages than the Simon’s algorithm.In the context of this study, we present an algorithm that combines Grover’s and Bernstein-Vazirani’s quantum algorithms. This algorithm empowers us to carry out key recovery attacks on Feistel structures. on Feistel structures, FX construction and Even Mansour construction. We exploit cryptosystems’ algebraic structure to launch successful key recovery attacks, considering that quantum attackers can only make classical queries. Through comparison, it can be concluded that this algorithm has stronger practicability in attacking block ciphers.
Tweakable block ciphers are more flexible than traditional block ciphers and widely used in modes of operation such as MAC and authenticated encryption. With the development of quantum computing, the threat of quantum algorithms to the security of cryptosystems is increasing. Research shows that some classical secure symmetric cryptographic constructions or schemes become vulnerable to the quantum attacks based on Simon's algorithm. This paper studies the security of tweakable block cipher constructions under quantum attacks based on Simon's algorithm, summarizes the quantum attack methods of Simon's algorithm and quantum-resistant constructions, and provides methods to enhance the quantum security of tweakable block ciphers.
The result of resource consumption in quantum attack implementation of cryptographic algorithm is an important metric to evaluate the security strength of cryptographic algorithm against quantum attack. This paper studies complete implementation of quantum attack on cryptographic algorithm using Grover meets Simon method. We find 9-round quantum distinguisher whose round is the longest currently about TWINE, and utilize Grover meets Simon method to carry out 14/15-round quantum key recovery attack on TWINE-80/TWINE-128 with lower complexity than exhaust attack. Furthermore, we give complete implementation of quantum oracle and QAA algorithm in TWINE’s quantum key recovery attack for the first time. The circuit is suitable for all implementation of quantum key recovery attack on block cipher using Grover meets Simon method.
Quantum algorithm is a key tool for cryptanalysis. At present, people are committed to building powerful quantum algorithms and tapping the potential of quantum algorithms, so as to further analyze the security of cryptographic algorithms under quantum computing. Recombining classical quantum algorithms is one of the current ideas to construct quantum algorithms. However, they cannot be easily combined, the feasibility of quantum algorithms needs further analysis in quantum environment. This paper reanalyzes the existing combined algorithm Grover-meets-Simon algorithm in terms of the principle of deferred measurement. First of all, due to the collapse problem caused by the measurement, we negate the measurement process of Simon's algorithm during the process of the Grover-meets-Simon algorithm. Second, since the output of the unmeasured Simon algorithm is quantum linear systems of equations, we discuss the solution of quantum linear systems of equations and find it feasible to consider the deferred measurement of the parallel Simon algorithm alone. Finally, since the Grover-meets-Simon algorithm involves an iterative problem, we reconsider the feasibility of the algorithm when placing multiple measurements at the end. According to the maximum probability of success and query times, we get that the Grover-meets-Simon algorithm is not an effective attack algorithm when putting the measurement process of the Simon algorithm in the iterative process at the end of Grover-meets-Simon algorithm.