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:2011.07022 · IACR Transactions on Cryptographic Hardware and Embedded Systems

Quantum Period Finding against Symmetric Primitives in Practice

Xavier Bonnetain, Samuel Jaques

Published Nov 19, 2021• 26 citations
arXivHTMLPDF

Abstract

We present the first complete descriptions of quantum circuits for the offline Simon’s algorithm, and estimate their cost to attack the MAC Chaskey, the block cipher PRINCE and the NIST lightweight finalist AEAD scheme Elephant. These attacks require a reasonable amount of qubits, comparable to the number of qubits required to break RSA-2048. They are faster than other collision algorithms, and the attacks against PRINCE and Chaskey are the most efficient known to date. As Elephant has a key smaller than its state size, the algorithm is less efficient and its cost ends up very close to or above the cost of exhaustive search.We also propose an optimized quantum circuit for boolean linear algebra as well as complete reversible implementations of PRINCE, Chaskey, spongent and Keccak which are of independent interest for quantum cryptanalysis. We stress that our attacks could be applied in the future against today’s communications, and recommend caution when choosing symmetric constructions for cases where long-term security is expected.

DOI
10.46586/tches.v2022.i1.1-27

Related papers

Efficient Implementation of PRESENT and GIFT on Quantum Computers

Kyungbae Jang, Gyeongju Song, Hyunjun Kim +3 more

Grover search algorithm is the most representative quantum attack method that threatens the security of symmetric key cryptography. If the Grover search algorithm is applied to symmetric key cryptography, the security level of target symmetric key cryptography can be lowered from n-bit to n2-bit. When applying Grover’s search algorithm to the block cipher that is the target of potential quantum attacks, the target block cipher must be implemented as quantum circuits. Starting with the AES block cipher, a number of works have been conducted to optimize and implement target block ciphers into quantum circuits. Recently, many studies have been published to implement lightweight block ciphers as quantum circuits. In this paper, we present optimal quantum circuit designs of symmetric key cryptography, including PRESENT and GIFT block ciphers. The proposed method optimized PRESENT and GIFT block ciphers by minimizing qubits, quantum gates, and circuit depth. We compare proposed PRESENT and GIFT quantum circuits with other results of lightweight block cipher implementations in quantum circuits. Finally, quantum resources of PRESENT and GIFT block ciphers required for the oracle of the Grover search algorithm were estimated.

Applied Sciences•May 23, 2021•54 citations

Optimized Implementation and Analysis of CHAM in Quantum Computing

Yujin Yang, Kyungbae Jang, Anubhab Baksi +1 more

A quantum computer capable of running the Grover search algorithm, which reduces the complexity of brute-force attacks by a square root, has the potential to undermine the security strength of symmetric-key cryptography and hash functions. Recently, studies on quantum approaches have proposed analyzing potential quantum attacks using the Grover search algorithm in conjunction with optimized quantum circuit implementations for symmetric-key cryptography and hash functions. Analyzing quantum attacks on a cipher (i.e., quantum cryptanalysis) and estimating the necessary quantum resources are related to evaluating post-quantum security for the target cryptography algorithms. In this paper, we revisit quantum implementations of CHAM block cipher, an ultra lightweight cipher, with a focus on optimizing the linear operations in its key schedule. We optimized the linear equations of CHAM as matrices by applying novel optimized decomposition techniques. Using the improved CHAM quantum circuits, we estimate the cost of Grover’s key search and evaluate the post-quantum security strength with further reduced costs.

Applied Sciences•Apr 20, 2023•8 citations

Analysis of Atom against quantum attacks

Ravi Anand, Rimpa Nandi, Takanori Isobe

Abstract A significant amount of study is being done to review the security promises made for the various ciphers now in use as a result of the development of quantum computing technology. A general attack against symmetric key cryptography primitives that can reduce search costs to the square root is Grover's search algorithm. To implement Grover's algorithm, it is necessary that the target cipher be implemented as a quantum circuit. Despite being relatively new, this area of study has received significant attention from the research community. The authors have estimated the cost of Grover's key search attack against the stream cipher Atom, for the first time, under circuit depth restrictions defined in National Institute of Standards and Technology (NIST) PQC standardisation process. The authors implement the quantum circuit of Atom in QISKIT, (open‐source software development kit for working with quantum computers running on IBM Quantum Experience). The results are also compared with other existing literature on LFSR‐based stream ciphers, such as Grain‐v1, Grain‐128‐AEAD, and Lizard. The authors also find that, to the best of their knowledge, in the existing literature on estimating the cost of Grover's attack on symmetric ciphers, Atom is the only 128‐bit key cipher that meets the threshold of ≈2 170 set by NIST for quantum security of 128‐bit key ciphers. The authors also analyse the security of Atom against quantum TMDTO attacks.

IET Quantum Communication•Nov 9, 2023•4 citations

Implementing Grover’s on AES-based AEAD schemes

Surajit Mandal, Ravi Anand, Mostafizar Rahman +2 more

Extensive research is currently underway to determine the security of existing ciphers in light of the advancements in quantum computing. Against symmetric key cryptography, Grover’s search algorithm is a prominent attack, capable of reducing search costs to the square root. For using Grover’s algorithm, it is imperative to embed the target cipher into a quantum circuit. Even so, this area of research is relatively new; it has garnered significant attention from the research community. In this study, we provide the first estimation of the cost of Grover’s key search attack against the AES-based AEAD schemes Rocca-S, AEGIS-128, and Tiaoxin-346. Our analysis considers circuit depth restrictions specified in NIST’s PQC standardization process. Considering NIST’s maximum depth constraints, We present the overall cost of these attacks using gate count and depth-times-width metrics. We observed that for $$\textsf{MAXDEPTH} = 2^{40}$$ , Rocca-S, AEGIS-128, and Tiaoxin-346 can be retrieved using Grover’s search algorithm with gate count of 1.09 × 2253, 1.14 × 2124, and 1.22 × 2124 respectively. Concerning the current updated values by NIST, these ciphers are secure in terms of the cost of implementing Grover’s attack for key recovery. The quantum circuits of these ciphers are implemented using QISKIT, an open-source software development kit (SDK) designed for working with quantum computers running on the IBM Quantum Experience platform.

Scientific Reports•Sep 10, 2024•9 citations

Quantum grover attack on MIBS

Hasan Özgür Çıldıroğlu, Harun Basmaci, Oğuz Yayla

Abstract The advent of quantum computing necessitates a rigorous reassessment of classical cryptographic primitives, particularly lightweight block ciphers (LBCs) deployed in resource-constrained environments. This work presents a comprehensive quantum implementation and security analysis of the Feistel-based LBC MIBS against quantum cryptanalysis. Using the inherent reversibility of its structure, we develop a novel ancilla-free quantum circuit that optimizes qubit count and depth. For MIBS-64 and MIBS-80, our implementation achieves quantum costs of 23,371 and 24,363, requiring 128 and 144 qubits, respectively, with a depth of 4,768. We subsequently quantify the cipher’s vulnerability to Grover’s key-search algorithm under the NIST PQC security constraint M A X D E P T H $\mathtt{M}\mathtt{A}\mathtt{X}\mathtt{D}\mathtt{E}\mathtt{P}\mathtt{T}\mathtt{H}$ . By constructing Grover oracles using inner parallelization with multiple plaintext-ciphertext pairs to suppress false positives, we demonstrate total quantum attack costs of approximately 2 94 for MIBS-64 and 2 111 for MIBS-80. These values fall below NIST’s Level-1 security threshold (2 170 ), confirming the susceptibility of both MIBS variants to quantum key-recovery attacks despite their classical lightweight efficiency.

Open Physics•Jan 1, 2026•0 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
We present the first complete descriptions of quantum circuits for the offline Simon’s algorithm, and estimate their cost to attack the MAC Chaskey, the block cipher PRINCE and the NIST lightweight finalist AEAD scheme Elephant. These attacks require a reasonable amount of qubits, comparable to the number of qubits required to break RSA-2048. They are faster than other collision algorithms, and the attacks against PRINCE and Chaskey are the most efficient known to date. As Elephant has a key smaller than its state size, the algorithm is less efficient and its cost ends up very close to or above the cost of exhaustive search.We also propose an optimized quantum circuit for boolean linear algebra as well as complete reversible implementations of PRINCE, Chaskey, spongent and Keccak which are of independent interest for quantum cryptanalysis. We stress that our attacks could be applied in the future against today’s communications, and recommend caution when choosing symmetric constructions for cases where long-term security is expected.
Grover search algorithm is the most representative quantum attack method that threatens the security of symmetric key cryptography. If the Grover search algorithm is applied to symmetric key cryptography, the security level of target symmetric key cryptography can be lowered from n-bit to n2-bit. When applying Grover’s search algorithm to the block cipher that is the target of potential quantum attacks, the target block cipher must be implemented as quantum circuits. Starting with the AES block cipher, a number of works have been conducted to optimize and implement target block ciphers into quantum circuits. Recently, many studies have been published to implement lightweight block ciphers as quantum circuits. In this paper, we present optimal quantum circuit designs of symmetric key cryptography, including PRESENT and GIFT block ciphers. The proposed method optimized PRESENT and GIFT block ciphers by minimizing qubits, quantum gates, and circuit depth. We compare proposed PRESENT and GIFT quantum circuits with other results of lightweight block cipher implementations in quantum circuits. Finally, quantum resources of PRESENT and GIFT block ciphers required for the oracle of the Grover search algorithm were estimated.
A quantum computer capable of running the Grover search algorithm, which reduces the complexity of brute-force attacks by a square root, has the potential to undermine the security strength of symmetric-key cryptography and hash functions. Recently, studies on quantum approaches have proposed analyzing potential quantum attacks using the Grover search algorithm in conjunction with optimized quantum circuit implementations for symmetric-key cryptography and hash functions. Analyzing quantum attacks on a cipher (i.e., quantum cryptanalysis) and estimating the necessary quantum resources are related to evaluating post-quantum security for the target cryptography algorithms. In this paper, we revisit quantum implementations of CHAM block cipher, an ultra lightweight cipher, with a focus on optimizing the linear operations in its key schedule. We optimized the linear equations of CHAM as matrices by applying novel optimized decomposition techniques. Using the improved CHAM quantum circuits, we estimate the cost of Grover’s key search and evaluate the post-quantum security strength with further reduced costs.
Abstract A significant amount of study is being done to review the security promises made for the various ciphers now in use as a result of the development of quantum computing technology. A general attack against symmetric key cryptography primitives that can reduce search costs to the square root is Grover's search algorithm. To implement Grover's algorithm, it is necessary that the target cipher be implemented as a quantum circuit. Despite being relatively new, this area of study has received significant attention from the research community. The authors have estimated the cost of Grover's key search attack against the stream cipher Atom, for the first time, under circuit depth restrictions defined in National Institute of Standards and Technology (NIST) PQC standardisation process. The authors implement the quantum circuit of Atom in QISKIT, (open‐source software development kit for working with quantum computers running on IBM Quantum Experience). The results are also compared with other existing literature on LFSR‐based stream ciphers, such as Grain‐v1, Grain‐128‐AEAD, and Lizard. The authors also find that, to the best of their knowledge, in the existing literature on estimating the cost of Grover's attack on symmetric ciphers, Atom is the only 128‐bit key cipher that meets the threshold of ≈2 170 set by NIST for quantum security of 128‐bit key ciphers. The authors also analyse the security of Atom against quantum TMDTO attacks.
Extensive research is currently underway to determine the security of existing ciphers in light of the advancements in quantum computing. Against symmetric key cryptography, Grover’s search algorithm is a prominent attack, capable of reducing search costs to the square root. For using Grover’s algorithm, it is imperative to embed the target cipher into a quantum circuit. Even so, this area of research is relatively new; it has garnered significant attention from the research community. In this study, we provide the first estimation of the cost of Grover’s key search attack against the AES-based AEAD schemes Rocca-S, AEGIS-128, and Tiaoxin-346. Our analysis considers circuit depth restrictions specified in NIST’s PQC standardization process. Considering NIST’s maximum depth constraints, We present the overall cost of these attacks using gate count and depth-times-width metrics. We observed that for MAXDEPTH=240\textsf{MAXDEPTH} = 2^{40}MAXDEPTH=240 , Rocca-S, AEGIS-128, and Tiaoxin-346 can be retrieved using Grover’s search algorithm with gate count of 1.09 × 2253, 1.14 × 2124, and 1.22 × 2124 respectively. Concerning the current updated values by NIST, these ciphers are secure in terms of the cost of implementing Grover’s attack for key recovery. The quantum circuits of these ciphers are implemented using QISKIT, an open-source software development kit (SDK) designed for working with quantum computers running on the IBM Quantum Experience platform.
Abstract The advent of quantum computing necessitates a rigorous reassessment of classical cryptographic primitives, particularly lightweight block ciphers (LBCs) deployed in resource-constrained environments. This work presents a comprehensive quantum implementation and security analysis of the Feistel-based LBC MIBS against quantum cryptanalysis. Using the inherent reversibility of its structure, we develop a novel ancilla-free quantum circuit that optimizes qubit count and depth. For MIBS-64 and MIBS-80, our implementation achieves quantum costs of 23,371 and 24,363, requiring 128 and 144 qubits, respectively, with a depth of 4,768. We subsequently quantify the cipher’s vulnerability to Grover’s key-search algorithm under the NIST PQC security constraint M A X D E P T H MAXDEPTH\mathtt{M}\mathtt{A}\mathtt{X}\mathtt{D}\mathtt{E}\mathtt{P}\mathtt{T}\mathtt{H}MAXDEPTH . By constructing Grover oracles using inner parallelization with multiple plaintext-ciphertext pairs to suppress false positives, we demonstrate total quantum attack costs of approximately 2 94 for MIBS-64 and 2 111 for MIBS-80. These values fall below NIST’s Level-1 security threshold (2 170 ), confirming the susceptibility of both MIBS variants to quantum key-recovery attacks despite their classical lightweight efficiency.
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.