ETSI TR 103 967 V1.1.1 (2025-01)

Cyber Security (CYBER); Quantum-Safe Cryptography (QSC); Impact of Quantum Computing on Symmetric Cryptography

DTR/CYBER-QSC-0022

General Information

• Status: Not Published
• Technical Committee: CYBER QSC - Quantum-Safe Cryptography
• Current Stage: 12 - Completion
• Due Date: 12-Feb-2025
• Completion Date: 29-Jan-2025

Standards Content (Sample)

TECHNICAL REPORT
Cyber Security (CYBER);
Quantum-Safe Cryptography (QSC);
Impact of Quantum Computing
on Symmetric Cryptography
2 ETSI TR 103 967 V1.1.1 (2025-01)

Reference
DTR/CYBER-QSC-0022
Keywords
cyber security, quantum safe cryptography
ETSI
650 Route des Lucioles
F-06921 Sophia Antipolis Cedex - FRANCE

Tel.: [phone]  Fax: [phone]

Siret N° 348 623 562 00017 - APE 7112B
Association à but non lucratif enregistrée à la
Sous-Préfecture de Grasse (06) N° w061004871

Important notice
The present document can be downloaded from the
ETSI Search & Browse Standards application.
The present document may be made available in electronic versions and/or in print. The content of any electronic and/or
print versions of the present document shall not be modified without the prior written authorization of ETSI. In case of any
existing or perceived difference in contents between such versions and/or in print, the prevailing version of an ETSI
deliverable is the one made publicly available in PDF format on ETSI deliver repository.
Users should be aware that the present document may be revised or have its status changed,
this information is available in the Milestones listing.
If you find errors in the present document, please send your comments to
the relevant service listed under Committee Support Staff.
If you find a security vulnerability in the present document, please report it through our
Coordinated Vulnerability Disclosure (CVD) program.
Notice of disclaimer & limitation of liability
The information provided in the present deliverable is directed solely to professionals who have the appropriate degree of
experience to understand and interpret its content in accordance with generally accepted engineering or
other professional standard and applicable regulations.
No recommendation as to products and services or vendors is made or should be implied.
No representation or warranty is made that this deliverable is technically accurate or sufficient or conforms to any law
and/or governmental rule and/or regulation and further, no representation or warranty is made of merchantability or fitness
for any particular purpose or against infringement of intellectual property rights.
In no event shall ETSI be held liable for loss of profits or any other incidental or consequential damages.

Any software contained in this deliverable is provided "AS IS" with no warranties, express or implied, including but not
limited to, the warranties of merchantability, fitness for a particular purpose and non-infringement of intellectual property
rights and ETSI shall not be held liable in any event for any damages whatsoever (including, without limitation, damages
for loss of profits, business interruption, loss of information, or any other pecuniary loss) arising out of or related to the use
of or inability to use the software.
Copyright Notification
No part may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying and
microfilm except as authorized by written permission of ETSI.
The content of the PDF version shall not be modified without the written authorization of ETSI.
The copyright and the foregoing restriction extend to reproduction in all media.

© ETSI 2025.
All rights reserved.
ETSI
3 ETSI TR 103 967 V1.1.1 (2025-01)
Contents
Intellectual Property Rights . 5
Foreword . 5
Modal verbs terminology . 5
1 Scope . 6
2 References . 6
2.1 Normative references . 6
2.2 Informative references . 6
3 Definition of terms, symbols and abbreviations . 8
3.1 Terms . 8
3.2 Symbols . 9
3.3 Abbreviations . 9
4 Introduction . 9
5 Grover's algorithm . 10
5.1 Overview . 10
5.2 Oracle implementation . 10
5.3 Parallelisation . 11
5.4 Maximum depth . 11
5.5 Quantum error correction . 12
5.6 Cycle time . 12
5.7 Discussion . 13
6 Impact of Grover on symmetric algorithms . 13
6.1 Considerations . 13
6.2 Block ciphers . 14
6.2.1 Logical costs for AES . 14
6.2.1.1 Methodology . 14
6.2.1.2 Selected AES Implementation . 15
6.2.1.3 Solution uniqueness . 15
6.2.1.4 Logical costs for AES key recovery . 16
6.2.2 Surface code costs for AES. 16
6.2.2.1 Assumptions . 16
6.2.2.2 Computational qubit costs . 17
6.2.2.3 Physical costs of AES key recovery . 18
6.2.3 Discussion of AES costs . 19
6.2.4 Other block ciphers . 20
6.3 Hash functions . 21
6.3.1 SHA-2 and SHA-3 . 21
6.3.1.1 Selected SHA-2 and SHA-3 Implementations . 21
6.3.1.2 Logical costs of SHA2 and SHA3 pre-image attacks . 21
6.3.1.3 Physical costs of SHA-2 and SHA-3 pre-image attacks. 22
7 Other quantum algorithms . 22
7.1 Quantum collision finding . 22
7.1.1 Overview . 22
7.1.2 BHT algorithm . 22
7.1.3 CNS algorithm . 23
7.2 Simon's algorithm . 23
7.3 Discussion . 24
8 Recommendations . 24
Annex A: Background on quantum error correction . 25
A.1 The planar surface code . 25
A.1.1 Overview . 25
ETSI
4 ETSI TR 103 967 V1.1.1 (2025-01)
A.1.2 Gate operations . 26
A.1.3 Magic state distillation . 26
A.1.3.1 Overview . 26
A.1.3.2 Bravyi-Kitaev distillation . 26
A.1.3.3 Litinski distillation . 27
Annex B: Change history . 29
History . 30

ETSI
5 ETSI TR 103 967 V1.1.1 (2025-01)
Intellectual Property Rights
Essential patents
IPRs essential or potentially essential to normative deliverables may have been declared to ETSI. The declarations
pertaining to these essential IPRs, if any, are publicly available for ETSI members and non-members, and can be
found in ETSI SR 000 314: "Intellectual Property Rights (IPRs); Essential, or potentially Essential, IPRs notified to
ETSI in respect of ETSI standards", which is available from the ETSI Secretariat. Latest updates are available on the
ETSI IPR online database.
Pursuant to the ETSI Directives including the ETSI IPR Policy, no investigation regarding the essentiality of IPRs,
including IPR searches, has been carried out by ETSI. No guarantee can be given as to the existence of other IPRs not
referenced in ETSI SR 000 314 (or the updates on the ETSI Web server) which are, or may be, or may become,
essential to the present document.
Trademarks
The present document may include trademarks and/or tradenames which are asserted and/or registered by their owners.
ETSI claims no ownership of these except for any which are indicated as being the property of ETSI, and conveys no
right to use or reproduce any trademark and/or tradename. Mention of those trademarks in the present document does
not constitute an endorsement by ETSI of products, services or organizations associated with those trademarks.
DECT™, PLUGTESTS™, UMTS™ and the ETSI logo are trademarks of ETSI registered for the benefit of its
Members. 3GPP™, LTE™ and 5G™ logo are trademarks of ETSI registered for the benefit of its Members and of the
3GPP Organizational Partners. oneM2M™ logo is a trademark of ETSI registered for the benefit of its Members and of ®
the oneM2M Partners. GSM and the GSM logo are trademarks registered and owned by the GSM Association.
Foreword
This Technical Report (TR) has been produced by ETSI Technical Committee Cyber Security (CYBER).
Modal verbs terminology
In the present document "should", "should not", "may", "need not", "will", "will not", "can" and "cannot" are to be
interpreted as described in clause 3.2 of the ETSI Drafting Rules (Verbal forms for the expression of provisions).
"must" and "must not" are NOT allowed in ETSI deliverables except when used in direct citation.

ETSI
6 ETSI TR 103 967 V1.1.1 (2025-01)
1 Scope
The present document gives an overview of the impact of quantum computing on symmetric algorithms such as block
ciphers and hash functions. It discusses the practicality of parallelising Grover's algorithm, the effect of limiting
quantum circuit depth, and the overhead from quantum error correction.
The present document supplements ETSI GR QSC 006 [i.1] by summarizing quantum resource estimates for attacks
against widely used symmetric algorithms with reasonable circuit depth assumptions. It also provides guidance on the
need to increase symmetric key lengths for a range of different use cases.
2 References
2.1 Normative references
Normative references are not applicable in the present document.
2.2 Informative references
References are either specific (identified by date of publication and/or edition number or version number) or
non-specific. For specific references, only the cited version applies. For non-specific references, the latest version of the
referenced document (including any amendments) applies.
NOTE: While any hyperlinks included in this clause were valid at the time of publication, ETSI cannot guarantee
their long term validity.
The following referenced documents are not necessary for the application of the present document but they assist the
user with regard to a particular subject area.
[i.1] ETSI GR QSC 006: "Quantum-Safe Cryptography (QSC); Limits to quantum computing applied
to symmetric key sizes".
[i.2] NIST SP 800-56B Rev. 2: "Recommendation for Pair-Wise Key-Establishment Using Integer
Factorization Cryptography".
[i.3] NIST SP 800-56A Rev. 3: "Recommendation for Pair-Wise Key-Establishment Schemes Using
Discrete Logarithm Cryptography".
[i.4] NIST FIPS 186-4: "Digital Signature Standard (DSS)".
[i.5] P.W. Shor: "Algorithms for quantum computation: discrete logarithms and factoring". Proceedings
th
35 Annual Symposium on Foundations of computer Science, 1994.
[i.6] C. Gidney and M. Ekerå: "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy
qubits". Quantum, 2021.
[i.7] M. Webber, V. Elfving, S. Weidt and W.K. Hensinger: "The impact of hardware specifications on
reaching quantum advantage in the fault tolerant regime". AVS Quantum Science, 2022.
[i.8] NIST IR 8413: "Status Report on the Third Round of the NIST Post-Quantum Cryptography
Standardization Process".
[i.9] NIST FIPS 197: "Advanced Encryption Standard (AES)".
[i.10] NIST FIPS 180-4: "Secure Hash Standard (SHS)".
[i.11] NIST FIPS 202: "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions".
th
[i.12] L.K. Grover: "A fast quantum mechanical algorithm for database search". Proceedings 28 Annual
ACM Symposium on Theory of Computing, 1996.
ETSI
7 ETSI TR 103 967 V1.1.1 (2025-01)
[i.13] C. Zalka: "Grover's quantum searching algorithm is optimal". Physical Review A 60.4 (1999).
[i.14] M. Boyer et al: "Tight bounds on quantum searching". Fortschritte der Physik: Progress of Physics
46.4‐5 (1998).
[i.15] NIST: "Submission requirements and evaluation criteria for the post-quantum cryptography
standardization process".
[i.16] A.G. Fowler et al: "Surface codes: Towards practical large-scale quantum computation".
Physical Review A 86.3 (2012).
[i.17] B. Eastin and E. Knill: "Restrictions on transversal encoded quantum gate sets". Physical Review
Letters 102.11 (2009).
[i.18] Shin-Yi Lin and Chih-Tsun Huang: "A High-Throughput Low-Power AES Cipher for
Network Applications". Asia and South Pacific Design Automation Conference (2007).
[i.19] Kyungbae Jang et al. "Quantum analysis of AES". Cryptology ePrint Archive (2022).
[i.20] Matthew Amy et al. "Estimating the cost of generic quantum pre-image attacks on SHA-2 and
SHA-3". International Conference on Selected Areas in Cryptography. Springer 2016,
pp. 317-337.
[i.21] Brassard et al.: "Quantum Algorithm for the Collision Problem". Third Latin American Symp. on
Theoretical Informatics (LATIN'98), pp. 163-169, 1998.
[i.22] S. Kutin: "Quantum Lower Bound for the Collision Problem with Small Range", THEORY OF
COMPUTING, Volume 1 (2005), pp. 29–36.
[i.23] P.C. van Oorschot and M.J. Wiener: "Parallel Collision Search with Cryptanalytic Applications".
Journal of Cryptology 12, 1–28 (1999).
[i.24] Y. Oh et al.: "Depth-optimized implementation of ASCON quantum circuit". Cryptology ePrint
Archive (2023).
[i.25] Kyungbae Jang et al.: "Improved Quantum Analysis of Speck and LowMC". INDOCRYPT 2022:
pp. 517-540.
[i.26] Z. Chen et al.: "Exponential suppression of bit or phase errors with cyclic error correction".
In: Nature 595 (July 2021), pp. 383–387.
[i.27] C. Ryan-Anderson et al.: "Realization of real-time fault-tolerant quantum error correction".
In: Physical Review X 11 (December 2021).
[i.28] S. Jaques et al.: "Implementing Grover oracles for quantum key search on AES and LowMC".
In: Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the
Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020,
Proceedings, Part II 30. 2020, pp. 280–310.
[i.29] A.G. Fowler, S.J. Devitt and C. Jones: "Surface code implementation of block code state
distillation". In: Scientific Reports 3.1 (June 2013).
[i.30] Bravyi and A. Kitaev.: "Universal quantum computation with ideal Clifford gates and noisy
ancillas". In: Physical Review A 71.2 (Febuary 2005).
[i.31] D. Litinski: "Magic state distillation: Not as costly as you think". In: Quantum 3 (Dec. 2019),
p. 205.
[i.32] BSI: "Status of quantum computer development" v2.0. 2023.
[i.33] L. Lao and B. Criger: "Magic state injection on the rotated surface code". In: Proceedings of the
th
19 ACM International Conference on Computing Frontiers. 2022, pp. 113–120.
[i.34] C. Gidney et al.: "Yoked surface codes". 2023. arXiv: 2312.04522 [quant-ph].
ETSI
8 ETSI TR 103 967 V1.1.1 (2025-01)
[i.35] Bathe, B., Anand, R. & Dutta, S.: "Evaluation of Grover's algorithm toward quantum cryptanalysis
on ChaCha". Quantum Inf Process 20, 394 (2021).
[i.36] Kyungbae Jang et al.: "Quantum Implementation and Analysis of SHA-2 and SHA-3". Cryptology
ePrint Archive (2024).
[i.37] Chailloux, A., Naya-Plasencia, M., Schrottenloher, A. (2017): "An Efficient Quantum Collision
Search Algorithm and Implications on Symmetric Cryptography". In: Takagi, T., Peyrin, T. (eds)
Advances in Cryptology - ASIACRYPT 2017. ASIACRYPT 2017. Lecture Notes in Computer
Science, vol 10625. Springer, Cham.
[i.38] Bernstein, D. J. (2009): "Cost analysis of hash collisions: will quantum computers make SHARCS
obsolete?". In SHARCS'09 Workshop Record (Proceedings 4th Workshop on Special-purpose
Hardware for Attacking Cryptograhic Systems, Lausanne, Switzerland, September 9-10, 2009)
(pp. 105-116).
[i.39] Bravyi, S., Cross, A.W., Gambetta, J.M. et al.: "High-threshold and low-overhead fault-tolerant
quantum memory". Nature 627, 778–782 (2024).
3 Definition of terms, symbols and abbreviations
3.1 Terms
For the purposes of the present document, the following terms apply:
circuit depth: number of sequential operations that are performed during the execution of a quantum circuit
circuit width: maximum number of operational qubits required during the execution of a quantum circuit
coherence time: length of time two qubits will remain in an entangled state before the external environment introduces
errors
magic state distillation: process for producing quantum states known as 'magic states', which are required to effect
particular quantum gates under a given Quantum Error Correction (QEC) scheme
EXAMPLE: When applying the surface code for QEC, magic state distillation is used to produce T-gates,
which can then be composed to other more complex gates, such as the Toffoli gate.
oracle function: black box quantum operator that transforms a quantum state |�⟩ → |�(�)⟩
qubit (logical): unit of quantum information analogous to a bit in classical computing
qubit (physical): physical device that behaves as a two-state quantum system
surface code: widely studied quantum error correction scheme that lays out physical qubits in a grid of data and
measurement qubits to produce a single logical qubit
NOTE: See Annex A.
T-gate: 2-qubit gate that can be composed to produce more complex gates, such as the Toffoli gate
Toffoli gate: 3-qubit gate that is an analogue of the AND gate in classical computing
uncomputation: process of reversing steps in a quantum circuit to cancel out intermediate quantum states that may
have been produced during calculations
ETSI
9 ETSI TR 103 967 V1.1.1 (2025-01)
3.2 Symbols
For the purposes of the present document, the following symbols apply:
O(f(x)) Big O notation. If g(x) = O(f(x)), then g(x) is bounded above asymptotically by f(x), up to a
constant multiple. More precisely, there is some x and some positive value M such that
|g(x)| < Mf(x) for all x > x .
Ω(f(x)) Big Omega notation. If g(x) = Ω(f(x)), then g(x) is bounded below asymptotically by f(x), up to a
constant multiple. More precisely, there is some x and some positive value M such that
|g(x)| > Mf(x) for all x > x .
⌊ ⌋
� Floor of �: the largest integer less than or equal to �.
⊕ Logical exclusive or (XOR) operation.
|�⟩ A ket in bra-ket notation. Denotes a quantum state.
EXAMPLE 1: |0⟩ denotes a single qubit in the collapsed basis state corresponding to a classical value of '0'.
�
EXAMPLE 2: (|0⟩ +|1⟩) denotes a single qubit in equal superposition between the basis states |0⟩ and |1⟩.
√�
3.3 Abbreviations
For the purposes of the present document, the following abbreviations apply:
AES Advanced Encryption Standard
ASIC Application Specific Integrated Circuit
ECDH Elliptic Curve Diffie-Hellman
ECDSA Elliptic Curve Digital Signature Algorithm
NIST National Institute of Standards and Technology
QEC Quantum Error Correction
RSA Public key algorithm invented by Rivest, Shamir and Adleman
SHA Secure Hash Algorithm
4 Introduction
Traditional public-key algorithms such as RSA [i.2], [i.4], Elliptic Curve Diffie-Hellman (ECDH) [i.3] and the Elliptic
Curve Digital Signature Algorithm (ECDSA) [i.4] are known to be vulnerable to polynomial-time quantum attacks via
Shor's algorithm [i.5]. It has been estimated that 2048-bit RSA could be broken in 8 hours on a device with 20 million
physical qubits [i.6] and that 256-bit ECDSA could be broken in a day on a device with 13 million physical qubits [i.7].
As a consequence, the US National Institute for Standards and Technology (NIST) are currently standardizing the next
generation of public-key algorithms [i.8].
Symmetric algorithms such as the AES [i.9] block cipher and the SHA-2 [i.10] and SHA-3 [i.11] hash functions are
believed to be immune to Shor. In most cases, the best-known quantum attack uses Grover's algorithm [i.12]. Grover
provides a generic square-root speed-up in the number of queries needed in an unstructured search problem (see
clause 5.1). This means that Grover could be used to find the 256-bit key for AES-256 with around 2 quantum
queries to the AES algorithm compared to the 2 queries expected for classical exhaustion.
However, assessing the cost of Grover in terms of the number of queries to the symmetric algorithm can be misleading.
It neglects overheads from:
• The cost of implementing the algorithm queried by Grover as a reversible quantum circuit (see clause 5.2);
• The cost of parallelising Grover so that a solution is found in a reasonable amount of time (see clause 5.3); and
• The cost of quantum error correction so that Grover succeeds with high enough probability (see clause 5.5).
ETSI GR QSC 006 [i.1] argues that 256-bit block ciphers and hash functions will remain secure until at least 2050 by
making conservative assumptions about the algorithm implementation, quantum error correction and quantum hardware
performance, and then estimating the amount of parallelisation available if an adversary is willing to spend a fraction of
their Gross Domestic Product on the attack.
ETSI
10 ETSI TR 103 967 V1.1.1 (2025-01)
The present document takes a different approach. It estimates the resources required to attack standardized block
ciphers (see clause 6.2) and hash functions (see clause 6.3) in a reasonable amount of time using the current state-of-
the-art for algorithm implementations and the most well-studied quantum error correction scheme (the surface code).
The present document also considers the impact of other quantum attacks on symmetric cryptography such as quantum
collision finding (see clause 7.1) and Simon's algorithm (see clause 7.2). Finally, it includes an assessment of the overall
threat to symmetric algorithms from quantum computing and concludes that migration efforts should be focused on
asymmetric cryptography (see clause 8).
5 Grover's algorithm
5.1 Overview
Grover's search algorithm is a quantum algorithm that can be applied to generic unstructured search problems to give an
asymptotic square-root speed-up over classical algorithms in terms of the number of queries needed. It has been shown
to be asymptotically optimal for such problems [i.13].
Let �:� → �0,1� be a function defined on a set � of size |�| = �. The unstructured search problem is to find an input
value � ∈ � such that ���� =1, when the function � does not have any properties that allow the input set to be
� �
searched more efficiently than simply evaluating � at values from �. If � � =1 for a unique � ∈ �, then it would take
classical search algorithms �/2 queries on average to find the solution �. Grover's algorithm, on the other hand, will
� �
find � with high probability after around �/4 √� quantum queries to �.
NOTE 1: If there are � solutions to ���� =1, then a classical search algorithm will take ���/�� queries to � to
find any such solution � and Grover's algorithm will find a solution with high probability after
��/4���/� quantum queries [i.14].
This setup can be applied naturally to the key recovery problem for block ciphers where a matched pair of input
� �
plaintext and output ciphertext values is known; that is, where Enc �,� = � for an unknown key �. Let � be the set
� �
of all possible key values and define the function �:� → 0,1 by:
� �
1 if Enc �,� = �,
���� = �
0otherwise.
���
EXAMPLE: For AES-128, the set of all possible key values has size � =2 so Grover's algorithm would
��
require on the order of 2 quantum queries to recover the key.
NOTE 2: Multiple matched input plaintext and output ciphertext pairs might be needed to uniquely determine the
key (see clause 6.2.1.3).
��� ��
However, comparing the headline figures of 2 classical queries with 2 quantum queries neglects significant details
of implementing Grover's algorithm on a quantum computer. The remainder of this clause will describe these details
and discuss the impact they have on estimating the required resources for an attack.
5.2 Oracle implementation
Grover's algorithm involves iterated queries to the oracle function �, which needs to be implemented on the quantum
computer.
The internal state of a quantum computer is often described in terms of qubits; that is, the quantum analogue of bits in a
classical computer. A quantum algorithm is then described as a quantum circuit built out of fundamental quantum gates
that operate on a few qubits at a time. The depth of a quantum circuit is the maximum number of sequential gate
operations that are performed during the computation.
The laws of quantum physics mean that all quantum gates, and all quantum circuits, need to be reversible. This means
that while some fundamental classical gates, such as XOR, translate directly to fundamental quantum gates, others, such
as AND, do not. Instead, the quantum analogue of the classical AND gate is the 3-qubit Toffoli gate which is in turn
constructed from several 1- and 2-qubit gates.
ETSI
11 ETSI TR 103 967 V1.1.1 (2025-01)
NOTE: The set of fundamental quantum gates supported, and their relative costs, will be dependent on the
underlying hardware so optimized implementations will need to be tailored to specific platforms.
The reversibility of quantum circuits also means that any qubits used for intermediate calculations cannot simply be
zeroed before re-use or the final measurement step; they need to be carefully uncomputed. This typically involves
performing the inverse circuit which adds further overheads to the implementation of the quantum oracle, both in the
number of required qubits and the depth of the circuit.
5.3 Parallelisation
In a classical brute force search, the probability of success is directly proportional to the runtime of the search: reducing
the runtime by a factor of � reduces the probability of success by the same factor, because the proportion of the input
space that can be explored is reduced by a factor of S. From a different perspective, the input space could be divided
between S processors, with each having a probability of success reduced by a factor of S. This means that parallelising
classical search by increasing the computational resources can reduce the time it takes to find a solution without
changing the total amount of work needed.
The same is not true for Grover's algorithm: it finds a solution with high probability in ��√�� sequential iterations of
the oracle function. There are two approaches for parallelising Grover's algorithm: inner and outer parallelisation.
• Inner parallelisation partitions the search space and performs a separate run of Grover's algorithm for each
�
partition. Reducing the runtime by a factor of � allows searching a space of size �/� with high success
�
probability, therefore requiring � processors to search the entire space.
• Outer parallelisation reduces the number of iterations of the oracle function for each instance, reducing the
probability of success of each individual instance and increasing the overall number of required instances. For
large �, reducing the number of oracle iterations by a factor of � in a Grover run reduces the probability of
� �
success by a factor of � [i.13], so it would require � processors to achieve the same overall success
probability.
For both approaches, in order to reduce the time it takes to find a solution by a factor of �, it is necessary to increase the
�
computational resources by a factor of � . That is, the total amount of work increases as more parallelisation is applied.
One advantage of inner parallelisation is that it reduces the impact of spurious results (see clause 6.2.1.3) since each
instance recovers its own potential solution. If the work is partitioned in such a way that the correct key is in a different
section of the search space from any spurious results, then it will still be recovered.
5.4 Maximum depth
During a single Grover instance, queries to the oracle function are made sequentially so the time taken to recover a
solution depends on the circuit depth for Grover; that is, the maximum number of sequential operations. When
estimating the security implications of Grover's algorithm, it is reasonable to place bounds on the length of time an
adversary will be prepared to wait. In combination with estimates for plausible cycle times (see clause 5.6), this bounds
the maximum depth of a single Grover run.
The total depth of a Grover run can be estimated as the depth of the circuit for a single query multiplied by the number
of iterations of the circuit. NIST [i.15] have suggested the following maximum circuit depths achievable under various
assumptions:
��
• 2 , which NIST cl [i.15]aimed approximately corresponded to the number of gates that near-term quantum
computing architectures could be expected to serially perform in one year;
��
• 2 , which NIST cl [i.15]aimed approximately corresponded to the number of gates that current classical
computing architectures could perform serially in 10 years; and
��
• 2 , which NIST cl [i.15]aimed approximately corresponded to the number of gates that atomic scale qubits
with speed of light propagation times could perform in 1 000 years.
In later clauses, the overheads introduced by quantum error correction, and estimates for a single cycle time are
discussed. Estimating a plausible cycle time of 200 ns [i.16], the following maximum circuit depths are included as
useful comparison points:
ETSI
12 ETSI TR 103 967 V1.1.1 (2025-01)
��
• 2 , which is approximately the number of 200 ns cycles that can be completed in two years; and
��
• 2 , which is approximately the number of 200 ns cycles that can be completed in 500 years.
The costings in later clauses will show that, in most cases, applying Grover's algorithm to standardized block ciphers
��
will require some degree of parallelisation to satisfy even the 2 gate limit for the overall circuit depth. This will incur
overheads in the resource estimation.
The other practical reason for restricting the maximum circuit depth is that it is not possible to checkpoint and restart
Grover in the same way as a long-running classical computation. If the computation is paused, the quantum state needs
to be maintained for the duration of the pause. If the quantum state is lost, the computation needs to restart from the
beginning. This places further constraints on the length of time that might be considered reasonable for a Grover run to
complete: not just the length of time that an adversary is prepared to wait, but the length of time a quantum processor,
and its classical supporting hardware, can be expected to run without a system malfunction or maintenance downtime.
5.5 Quantum error correction
It is important to distinguish between the logical qubits and quantum gates that are used to describe quantum algorithms
and the physical qubits and quantum gates that are implemented in quantum hardware.
Logical qubits are high-fidelity and long-lived. Physical qubits are inherently noisy and short-lived due to the difficulty
of isolating them from the external environment. When the information stored in a quantum state is affected by
interactions with the external environment, the state is said to have decohered. The coherence time of a physical qubit is
the length of time it can maintain a quantum state before errors arise.
In classical error correction, a signal is transmitted over a noisy channel. The intended message can be encoded using an
error correction scheme that duplicates and spreads the information over several bits within the transmission. The
recipient of the signal measures a syndrome (pattern of errors), decodes it to deduce the most likely transmission
error(s) and then applies any necessary corrections to recover the original message. Analogously, quantum information
can be redundantly encoded over several noisy physical qubits using a quantum error correction scheme.
Most quantum algorithms, including Grover's algorithm, will require quantum error correction to construct individual
logical qubits from groups of physical qubits. This is needed both for maintaining information stored in idle qubits and
for correcting errors when quantum gates are applied. Longer quantum algorithms will have a higher probability of an
error occurring and so require stronger error correction to prevent this.
Applying quantum error correction adds overheads to the implementation of quantum algorithms, both in the number of
physical qubits required and in the time taken to apply logical gate operations. The exact costs will vary depending on
the physical qubit and quantum gate error rates achieved in the underlying hardware, and the error correction scheme
that is applied.
EXAMPLE: The planar surface code is used by Gidney et al. in [i.6] to provide an estimate of the physical
qubit and time resources for recovering a 2048-bit RSA key via Shor's algorithm. An overview of
this error correction scheme is given in clause A.1.
NOTE: For a given error correction scheme to apply, the physical qubit coherence times and physical gate
fidelities need to meet certain minimum thresholds.
For any error correction scheme, there will be logical gates that are not compatible with the error correction and cannot
be implemented directly on the logical qubits [i.17]. These logical gates require the use of high-accuracy quantum states
produced through a process known as magic state distillation and so can be substantially more expensive than other
gates. For a more detailed description of this process when using the planar surface code, see clause A.1.3.
5.6 Cycle time
Quantum error correction involves several rounds of quantum syndrome measurement, classical processing, and qubit
correction. The reaction time of an error correcting code is the time taken to complete one such round. The costs
presented here account for quantum operations in terms of measurement time only, i.e. each cycle is costed as the time
needed for one round of syndrome measurements. In other words, they neglect the classical processing and qubit
correction.
ETSI
13 ETSI TR 103 967 V1.1.1 (2025-01)
A cycle is the time taken to execute a basic quantum gate on a single logical qubit or pair of qubits. The exact cycle
time will vary depending on the physical qubit and quantum gate performance achieved in the underlying hardware, and
the error correction scheme that is applied. For example, Google's superconducting qubit platform Sycamore achieved a
cycle time of around 1 µs in 2022 [i.26], whereas Honeywell's trapped ion qubit platform achieved a cycle time of
around 200 ms in 2021 [i.27]. Often, the cycle time is dominated by the qubit initialization and measurement times.
Current superconducting qubit technology can achieve 140 ns initialization and measurement gate times with an error
−3
rate slightly above 10 . Ion trap hardware is slower with 50 µs initialization and 30 µs measurement gates for a similar
error rate.
The present document follows [i.16] and takes 200 ns as a plausible cycle time. In comparison, the RSA [i.6] and
ECDH [i.7] results assumed a 1 μs cycle time, although the performance was limited by the reaction time. Table 1
illustrates the impact of different choices of maximum depth and achievable cycle time on the length of time taken for a
computation of a given maximum depth.
Table 1: Length of time taken for a given maximum depth
Cycle time
Maximum
depth 1 μs 200 ns 1 ns
2 12,7 days 2,55 days 18,3 minutes
2 8,92 years 1,78 years 3,26 days
2 2 280 years 457 years 2,28 years
2 585 000 years 117 000 years 585 years

5.7 Discussion
There are multiple considerations when it comes to implementing Grover's search algorithm on a quantum computer.
This complicates the task of estimating the resources required to attack a particular block cipher or hash function.
There are estimates in the academic literature for the logical resources required to implement the oracle function for
standard block ciphers and hash functions. However, these can take different approaches to optimization depending on
whether the goal is to minimize the number of qubits, the number of gates, or the circuit depth. When the error
correction is assumed to use surface codes, the resource estimates often try to minimize the number of T-gates (a basic
quantum gate, which more complicated gates are often decomposed into) since these would be expensive to implement.
NIST [i.15] have suggested different bounds for the maximum circuit depth which correspond to assumptions about the
number of quantum gates that can be applied sequentially in a given time period. Alternative bounds can be derived
from plausible limits on the performance of error correction. The total circuit depth for Grover's algorithm then
determines the amount of parallelisation needed.
Finally, it will be necessary to include the overhead from error correction to give estimates for the physical resources
required.
Clause 6 provides a methodology for estimating these costs, leading to overall resource estimates for applying Grover's
algorithm to selected block ciphers and hash functions.
6 Impact of Grover on symmetric algorithms
6.1 Considerations
The resources required to apply Grover's algorithm to a symmetric algorithm include both the time taken and the cost of
the physical hardware required to perform the attack. This clause will describe the methodology used to produce
resource estimates for a variety of symmetric algorithms. Resource estimates will be given using each of the maximum
depth choices given in clause 5.4 to provide plausible bounds for the number of operations a quantum computer can
perform in a single run.
ETSI
14 ETSI TR 103 967 V1.1.1 (2025-01)
There are multiple implementations of symmetric algorithms for quantum architectures available in the current
literature, targeting different aspects of optimization such as the maximum number of qubits in use (width) or the
number of cycles required to complete a single iteration of the algorithm (depth). Once an implementa
...