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:1808.03266

A quantum related-key attack based on Bernstein-Vazirani algorithm

Huiqin Xie, Li Yang

Published Aug 9, 2018• 2 citations
arXivHTMLPDF

Abstract

Due to the powerful computing capability of quantum computers, cryptographic researchers have applied quantum algorithms to cryptanalysis and obtained many interesting results in recent years. In this paper, we study related-key attack in the quantum setting, and proposed a specific related-key attack which can recover the key of block ciphers efficiently, as long as the attacked block ciphers satisfy certain conditions. The attack algorithm employs Bernstein-Vazirani algorithm as a subroutine and requires the attacker to query the encryption oracle with quantum superpositions. Afterwards, we rigorously demonstrate the validity of the attack and analyze its complexity. Our work shows that related-key attack is quite powerful when combined with quantum algorithms, and provides some guidance for the design of block ciphers that are secure against quantum adversaries.

DOI
10.48550/arxiv.1808.03266

Related papers

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 on MIBS Block Cipher Based on Bernstein–Vazirani Algorithm

Huiqin Xie, Zhangmei Zhao, Ke Wang +2 more

Because of the substantial progress in quantum computing technology, the safety of traditional cryptologic schemes is facing serious challenges. In this study, we explore the quantum safety of the lightweight cipher MIBS and propose quantum key-recovery attacks on the MIBS cipher by utilizing Grover’s algorithm and Bernstein–Vazirani algorithm. We first construct linear-structure functions based on the 5-round MIBS cipher according to the characteristics of the linear transformations, and then we obtain a quantum distinguisher of the 5-round MIBS cipher by applying Bernstein–Vazirani algorithm to the constructed functions. Finally, utilizing this distinguisher and Grover’s algorithm, we realize a 7-round key-recovery attack on the MIBS cipher, and then we expand the attack to more rounds of MIBS based on a similar idea. The quantum attack on the 7-round MIBS requires 156 qubits and has a time complexity of 210.5. An 8-round attack requires 179 qubits and has a time complexity of 222. Compared with existing quantum attacks, our attacks have better time complexity when attacking the same number of rounds.

Mathematics•Aug 28, 2024•2 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

On Quantum Related-Key Attacks on Iterated Even-Mansour Ciphers

Akinori Hosoyamada, Kazumaro Aoki

It has been said that security of symmetric key schemes is not so much affected by quantum computers, compared to public key schemes. However, recent works revealed that, in some specific situations, symmetric key schemes are also broken in polynomial time by adversaries with quantum computers. These works contain a quantum distinguishing attack on 3-round Feistel ciphers and a quantum key recovery attack on the Even-Mansour cipher by Kuwakado and Morii, in addition to the quantum forgery attack on CBC-MAC which is proposed independently by Kaplan et al., and by Santoli and Schaffner. Iterated Even-Mansour cipher is a simple but important block cipher, which can be regarded as an idealization of AES. Whether there exists an efficient quantum algorithm that can break iterated Even-Mansour cipher with independent subkeys is an important problem from the viewpoint of analyzing post-quantum security of block ciphers. Actually there is an efficient quantum attack on iterated Even-Mansour cipher by Kaplan et al., but their attack can only be applied in the case that all subkeys are the same. This paper shows that there is a polynomial time quantum algorithm that recovers partial keys of the iterated Even-Mansour cipher with independent subkeys, in a related-key setting. The related-key condition is somewhat strong, but our algorithm can recover subkeys with two related oracles. In addition, we also show that our algorithm can recover all keys of the i-round iterated Even-Mansour cipher, if we are allowed to access i related quantum oracles. To realize quantum related-key attacks, we extend Simon's quantum algorithm so that we can recover the hidden period of a function that is periodic only up to constant. Our technique is to take differential of the target function to make a double periodic function, and then apply Simon's algorithm.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Dec 31, 2018•20 citations

Quantum differential cryptanalysis based on Bernstein-Vazirani algorithm

Rong-Xue Xu, Hongwei Sun, Kejia Zhang +2 more

Abstract Recent research has demonstrated the potential of quantum algorithms to exploit vulnerabilities in various popular constructions, such as certain block ciphers like Feistel, Even-Mansour, and multiple MACs, within the superposition query model. In this study, we delve into the security of block ciphers against quantum threats, particularly investigating their susceptibility to cryptanalysis techniques, notably exploring quantum adaptations of differential cryptanalysis. Initially, we introduce a BV-based quantum algorithm for identifying linear structures with a complexity of $O(n)$ O ( n ) , where n denotes the number of bits in the function. Subsequently, we illustrate the application of this algorithm in devising quantum differential cryptanalysis techniques, including quantum differential cryptanalysis, quantum small probability differential cryptanalysis, and quantum impossible differential cryptanalysis, demonstrating polynomial acceleration compared to prior approaches. By treating the encryption function as a unified entity, our algorithm circumvents the traditional challenge of extending differential paths in differential cryptanalysis.

EPJ Quantum Technology•Dec 1, 2024•6 citations

A note on quantum related-key attacks

Martin Roetteler, Rainer Steinwandt

In a basic related-key attack against a block cipher, the adversary has access to encryptions under keys that differ from the target key by bit-flips. In this short note we show that for a quantum adversary such attacks are quite powerful: if the secret key is (i) uniquely determined by a small number of plaintext-ciphertext pairs, (ii) the block cipher can be evaluated efficiently, and (iii) a superposition of related keys can be queried, then the key can be extracted efficiently.

arXiv:1306.2301•Jun 10, 2013•0 citations
Due to the powerful computing capability of quantum computers, cryptographic researchers have applied quantum algorithms to cryptanalysis and obtained many interesting results in recent years. In this paper, we study related-key attack in the quantum setting, and proposed a specific related-key attack which can recover the key of block ciphers efficiently, as long as the attacked block ciphers satisfy certain conditions. The attack algorithm employs Bernstein-Vazirani algorithm as a subroutine and requires the attacker to query the encryption oracle with quantum superpositions. Afterwards, we rigorously demonstrate the validity of the attack and analyze its complexity. Our work shows that related-key attack is quite powerful when combined with quantum algorithms, and provides some guidance for the design of block ciphers that are secure against quantum adversaries.
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.
Because of the substantial progress in quantum computing technology, the safety of traditional cryptologic schemes is facing serious challenges. In this study, we explore the quantum safety of the lightweight cipher MIBS and propose quantum key-recovery attacks on the MIBS cipher by utilizing Grover’s algorithm and Bernstein–Vazirani algorithm. We first construct linear-structure functions based on the 5-round MIBS cipher according to the characteristics of the linear transformations, and then we obtain a quantum distinguisher of the 5-round MIBS cipher by applying Bernstein–Vazirani algorithm to the constructed functions. Finally, utilizing this distinguisher and Grover’s algorithm, we realize a 7-round key-recovery attack on the MIBS cipher, and then we expand the attack to more rounds of MIBS based on a similar idea. The quantum attack on the 7-round MIBS requires 156 qubits and has a time complexity of 210.5. An 8-round attack requires 179 qubits and has a time complexity of 222. Compared with existing quantum attacks, our attacks have better time complexity when attacking the same number of rounds.
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.
It has been said that security of symmetric key schemes is not so much affected by quantum computers, compared to public key schemes. However, recent works revealed that, in some specific situations, symmetric key schemes are also broken in polynomial time by adversaries with quantum computers. These works contain a quantum distinguishing attack on 3-round Feistel ciphers and a quantum key recovery attack on the Even-Mansour cipher by Kuwakado and Morii, in addition to the quantum forgery attack on CBC-MAC which is proposed independently by Kaplan et al., and by Santoli and Schaffner. Iterated Even-Mansour cipher is a simple but important block cipher, which can be regarded as an idealization of AES. Whether there exists an efficient quantum algorithm that can break iterated Even-Mansour cipher with independent subkeys is an important problem from the viewpoint of analyzing post-quantum security of block ciphers. Actually there is an efficient quantum attack on iterated Even-Mansour cipher by Kaplan et al., but their attack can only be applied in the case that all subkeys are the same. This paper shows that there is a polynomial time quantum algorithm that recovers partial keys of the iterated Even-Mansour cipher with independent subkeys, in a related-key setting. The related-key condition is somewhat strong, but our algorithm can recover subkeys with two related oracles. In addition, we also show that our algorithm can recover all keys of the i-round iterated Even-Mansour cipher, if we are allowed to access i related quantum oracles. To realize quantum related-key attacks, we extend Simon's quantum algorithm so that we can recover the hidden period of a function that is periodic only up to constant. Our technique is to take differential of the target function to make a double periodic function, and then apply Simon's algorithm.
Abstract Recent research has demonstrated the potential of quantum algorithms to exploit vulnerabilities in various popular constructions, such as certain block ciphers like Feistel, Even-Mansour, and multiple MACs, within the superposition query model. In this study, we delve into the security of block ciphers against quantum threats, particularly investigating their susceptibility to cryptanalysis techniques, notably exploring quantum adaptations of differential cryptanalysis. Initially, we introduce a BV-based quantum algorithm for identifying linear structures with a complexity of O(n)O(n)O(n) O ( n ) , where n denotes the number of bits in the function. Subsequently, we illustrate the application of this algorithm in devising quantum differential cryptanalysis techniques, including quantum differential cryptanalysis, quantum small probability differential cryptanalysis, and quantum impossible differential cryptanalysis, demonstrating polynomial acceleration compared to prior approaches. By treating the encryption function as a unified entity, our algorithm circumvents the traditional challenge of extending differential paths in differential cryptanalysis.