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

arXiv:2002.12439 · Lecture notes in computer science

Quantum Attacks Without Superposition Queries: The Offline Simon’s Algorithm

Xavier Bonnetain, Akinori Hosoyamada, María Naya‐Plasencia, Yu Sasaki, André Schrottenloher

Published Jan 1, 2019• 121 citations
arXivHTMLPDF
DOI
10.1007/978-3-030-34578-5_20

Related papers

Quantum Attacks: A View of Data Complexity on Offline Simon’s Algorithm

Bo Yu, Tairong Shi, Xiaoyang Dong +3 more

Lecture notes in computer science•Jan 1, 2024•3 citations

Applications of Simon’s algorithm in quantum attacks on Feistel variants

Cui Jingyi, Jiansheng Guo, Shuzhen Ding

Quantum Information Processing•Mar 1, 2021•25 citations

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

Bao-Min Zhou, Zheng Yuan

Quantum Information Processing•Sep 2, 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

Cryptanalysis Against Symmetric-Key Schemes with Online Classical Queries and Offline Quantum Computations

Akinori Hosoyamada, Yu Sasaki

Lecture notes in computer science•Jan 1, 2018•59 citations

Quantum Key-Recovery Attacks on Permutation-Based Pseudorandom Functions

Hong-Wei Sun, Fei Gao, Rong-Xue Xu +3 more

Due to their simple security assessments, permutation-based pseudo-random functions (PRFs) have become widely used in cryptography. It has been shown that PRFs using a single n-bit permutation achieve n/2 bits of security, while those using two permutation calls provide 2n/3 bits of security in the classical setting. This paper studies the security of permutation-based PRFs within the Q1 model, where attackers are restricted to classical queries and offline quantum computations. We present improved quantum-time/classical-data tradeoffs compared with the previous attacks. Specifically, under the same assumptions/hardware as Grover’s exhaustive search attack, i.e. the offline Simon algorithm, we can recover keys in quantum time Õ(2n/3), with O(2n/3) classical queries and O(n2) qubits. Furthermore, we enhance previous superposition attacks by reducing the data complexity from exponential to polynomial, while maintaining the same time complexity. This implies that permutation-based PRFs become vulnerable when adversaries have access to quantum computing resources. It is pointed out that the above quantum attack can be applied to several cryptographic schemes, including PDMMAC and pEDM, as well as general instantiations like XopEM, EDMEM, EDMDEM, and others.

IEEE Internet of Things Journal•Jun 12, 2025•7 citations
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.
Due to their simple security assessments, permutation-based pseudo-random functions (PRFs) have become widely used in cryptography. It has been shown that PRFs using a single n-bit permutation achieve n/2 bits of security, while those using two permutation calls provide 2n/3 bits of security in the classical setting. This paper studies the security of permutation-based PRFs within the Q1 model, where attackers are restricted to classical queries and offline quantum computations. We present improved quantum-time/classical-data tradeoffs compared with the previous attacks. Specifically, under the same assumptions/hardware as Grover’s exhaustive search attack, i.e. the offline Simon algorithm, we can recover keys in quantum time Õ(2n/3), with O(2n/3) classical queries and O(n2) qubits. Furthermore, we enhance previous superposition attacks by reducing the data complexity from exponential to polynomial, while maintaining the same time complexity. This implies that permutation-based PRFs become vulnerable when adversaries have access to quantum computing resources. It is pointed out that the above quantum attack can be applied to several cryptographic schemes, including PDMMAC and pEDM, as well as general instantiations like XopEM, EDMEM, EDMDEM, and others.