The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index; none of the 32 sources its claims cite is checked for support yet.
Implementing Grover Oracles for Quantum Key Search on AES and LowMC
Open accessAbstract
Grover’s search algorithm gives a quantum attack against block ciphers by searching for a key that matches a small number of plaintext-ciphertext pairs. This attack uses \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\sqrt{N})$$\end{document}O(N) calls to the cipher to search a key space of size N. Previous work in the specific case of AES derived the full gate cost by analyzing quantum circuits for the cipher, but focused on minimizing the number of qubits. In contrast, we study the cost of quantum key search attacks under a depth restriction and introduce techniques that reduce the oracle depth, even if it requires more qubits. As cases in point, we design quantum circuits for the block ciphers AES and LowMC. Our circuits give a lower overall attack cost in both the gate count and depth-times-width cost models. In NIST’s post-quantum cryptography standardization process, security categories are defined based on the concrete cost of quantum key search against AES. We present new, lower cost estimates for each category, so our work has immediate implications for the security assessment of post-quantum cryptography. As part of this work, we release Q# implementations of the full Grover oracle for AES-128, -192, -256 and for the three LowMC instantiations used in Picnic, including unit tests and code to reproduce our quantum resource estimates. To the best of our knowledge, these are the first two such full implementations and automatic resource estimations.
Overview
AI snapshot
Written from the paper’s full text.
TL;DR
The paper presents Q# implementations of full Grover oracles for AES-128/192/256 and the three LowMC instances used in Picnic, optimizing for depth under NIST’s MAXDEPTH rather than qubit width. It reports lower gate and depth-times-width costs than prior AES circuits and derives new, lower NIST security-category estimates, with an 11–13 bit gate-cost reduction.
Key findings
- The authors release Q# implementations of the full Grover oracle for AES-128, -192, -256 and for the three LowMC instantiations used in Picnic, including unit tests and code to reproduce resource estimates; they state these are the first two such full implementations and automatic resource estimations.
- Under a depth restriction, inner parallelization and depth-optimized circuits reduce costs: for AES-128 key search without a depth limit, G-cost is 1.34·2^83 gates and DW-cost is 1.75·2^86 qubit-cycles; with MAXDEPTH = 2^40, G-cost rises to 1.07·2^117 and DW-cost to 1.76·2^120, while with MAXDEPTH = 2^64, G-cost is 1.07·2^93.
- For NIST categories, the paper reports a consistent gate-cost reduction of 11–13 bits: e.g. category 1 (AES-128) at MAXDEPTH = 2^40 is 1.07·2^117 versus NIST’s 2^130, and at MAXDEPTH = 2^64 is 1.07·2^93 versus 2^106; category 3 at 2^40 is 1.09·2^181 versus 2^193; category 5 at 2^40 is 1.39·2^245 versus 2^258. The exception is category 1 with MAXDEPTH = 2^96, where this work gives 1.34·2^83 versus NIST’s 2^74.
- LowMC L1 can be broken with G-cost 1.25·2^123 in depth MAXDEPTH = 2^40, while the original NIST category 1 bound requires a scheme not to be broken by an attack using less than 2^130 gates; despite LowMC’s lower T-gate count, its large CNOT count leads to higher G-cost and DW-cost than AES when all gates are counted.
Methods
- Design: Q# circuits for AES and LowMC using Clifford+T gates, AND gates, PLU decompositions for linear maps, in-place AES key expansion, and Maximov’s MixColumn; resource estimates are obtained automatically from the Q# compiler, with unit tests against Python/PyCryptodome and the LowMC C++ reference.
- Grover analysis: key search uses r plaintext-ciphertext pairs, with spurious-key probabilities derived under pseudo-random permutation/function heuristics; under MAXDEPTH, the paper uses inner parallelization by dividing the key space and evaluates G-cost and depth-times-width (DW-cost) metrics.
- Data/sample: AES-128/192/256 and the three LowMC parameter sets (128, 192, 256) used in Picnic; the main analysis is resource estimation from the Q# implementations and comparison to prior work and NIST formulas.
Limitations
- Stated: the paper ignores layout and communication costs, assumes full parallelism and free rewiring, and notes that the Q# compiler cannot optimize small circuit variations; measurement-based gate counts are probabilistic because PRNG seeding is unsupported.
- Stated: the LowMC implementation uses the original LowMC design and is suboptimal, and the authors defer a final conclusion on relative LowMC-vs-AES security until LowMC circuits are optimized to a similar extent.
- Evident from the text: resource estimates depend on the specific Q# compiler/QDK versions and assumptions, and the security-category implications rely on heuristic block-cipher assumptions and chosen MAXDEPTH values rather than a modeled physical fault-tolerant architecture.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Figures
![Fig. 1 Alternative circuits implementing the same linear transformation M : F 4 2 → F 4 2 , by using the two strategies described in § 3.3. Both are direct implementations, and could potentially be reduced in size by automatic means as in [MSR + 19], [MSC + 19], [GKMR14] and [ZC19], or manually. Figure 1b is wider and has a larger gate count, but is shallower, than Figure 1c.](/paper-figures/8f023d518d9e4bf084d3d37133653e71/implementing-grover-oracles-for-quantum-key-search-on-aes-and-lowmc-figure-1.png)
Verification
Claims the paper makes
34 Own interpretation · 34 No basis given · 25 Own result · 23 Sources not found · 2 Not checked yet · 2 Own method
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“We see a consistent gate cost reduction between 11 and 13 bits, making it easier for submitters to claim a certain quantum security category.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- The authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
- The authors state this as an assumption: MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“It follows that for a single message block of length n , Pr K = K ′ ( C K ( m ) = C K ′ ( m )) = 2 -n .”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- The authors state this as an assumption: Under a fixed key K, the map m -> C_K(m) is a pseudo-random permutation; under a fixed message block m, the map K -> C_K(m) is a pseudo-random function.
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“We also give a rigorous justification for the number of plaintext-ciphertext blocks needed in Grover's oracle in the context of parallelization. Smaller values than those proposed by Grassl et al. [GLRS16] are sufficient, as is also pointed out by Langenberg et al. [LPS19].”
What the sources say
- Not matchedcites [GLRS16]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [LPS19]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- The authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
- The authors state this as an assumption: MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
- Not matched
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Thus we can choose r such that rn is slightly larger than k ; rn = k +10 gives Pr( X = 0) ≈ 0 . 999.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- The authors state this as an assumption: Under a fixed key K, the map m -> C_K(m) is a pseudo-random permutation; under a fixed message block m, the map K -> C_K(m) is a pseudo-random function.
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“Favoring lower depth at the cost of a slightly larger width in the oracle circuit leads to costs that are smaller in both metrics than for the circuits presented in [GLRS16], [ASAM18] and [LPS19].”
What the sources say
- Not matchedcites [GLRS16]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [ASAM18]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [LPS19]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: unclear — It is unclear why the paper says it holds.
- The authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
- The authors state this as an assumption: MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
- Not matched
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Since the number of keys different from K is 2 k -1, we expect the number of spurious keys for an r -block message to be (2 k -1)2 -rn .”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- The authors state this as an assumption: Under a fixed key K, the map m -> C_K(m) is a pseudo-random permutation; under a fixed message block m, the map K -> C_K(m) is a pseudo-random function.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“In a block cipher where k = b · n is a multiple of n , taking r = b +1 will give the unique key K with probability at least 1 -2 -n , which is negligibly close to 1 for typical block sizes.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- The authors state this as an assumption: Under a fixed key K, the map m -> C_K(m) is a pseudo-random permutation; under a fixed message block m, the map K -> C_K(m) is a pseudo-random function.
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“Overall, the [BP12] S-box leads to a more cost effective circuit for our purposes in both the G -cost and DW -cost metrics, and hence we did not proceed further in our analysis of costs using the [BP10] design.”
What the sources say
- Not matchedcites BP12
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites BP10
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Not matched
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“This circuit uses 4 T gates and 11 Clifford gates in T-depth 1 and total depth 8.”
What the sources say
- Not matchedcites [Sel13]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [Gid18]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Not matched
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“We would thus expect the T-depth of n rounds of AES to be 2 n times the T-depth of the S-box. Instead, Table 3 shows smaller depths.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- It may state two separate claims as one. 44
- The quote only partly states this claim. 1
- Probably not a substantial claim. 19
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“As part of this work, we release Q# implementations of the full Grover oracle for AES-128, -192, -256 and for the three LowMC instantiations used in Picnic, including unit tests and code to reproduce our quantum resource estimates.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Our circuits give a lower overall attack cost in both the gate count and depth-times-width cost models.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
The quote only partly states this claim.
- The authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
- The authors state this as an assumption: MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“To the best of our knowledge, our work results in the most shallow quantum implementation of AES proposed so far, and the first ever for LowMC.”
hedged- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
- The authors state this as an assumption: MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
In the paper
“We present new, lower cost estimates for each category, so our work has immediate implications for the security assessment of post-quantum cryptography.”
What the sources say
- Not matchedcites [NIS16]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
- The authors state this as an assumption: MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
- Not matched
In the paper
“Note that the results obtained here differ from the ones presented in [LPS19, § 3.2]. This is due to the difference in counting gates and depth. While [LPS19] counts Toffoli gates, the Q# resource estimator costs at a lower level of T gates and also counts all gates needed to implement a Toffoli gate.”
What the sources say
- Not matchedcites LPS19
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Not matched
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“A single oracle circuit uses relatively few logical qubits ( < 2 20 ), so these costs are unlikely to dominate.”
hedgedconditional- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: fails — The paper may give no reason why it holds.
Probably not a substantial claim. The paper may give no reason why it holds. It may state two separate claims as one.
- The authors state this as an assumption: Layout and communication costs for the Grover oracle circuit are ignored.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Our experiments show that without a depth restriction, it seems advantageous to use the in-place version to minimize both G -cost and DW -cost metrics, while for a depth restricted setting, Maximov's circuit seems better due to the square in the depth term in Equation (10).”
hedgedconditional- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“For LowMC-128, 192, and 256 the minimum depths are respectively 2 41 . 1 c s , 2 59 . 8 c s and 2 76 . 4 c s .”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Instead, we propose to minimize width by not requiring ancilla qubits at all. At the same time, we are able to reduce the depth in comparison with the naive key expansion using ancilla qubits for all key bits as described above.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: unclear — It is unclear why the paper says it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“The probability for a unique K is Pr( X = 0) ≈ 1 /e ≈ 0 . 3679, and the probability of exactly one spurious key is the same.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: Under a fixed key K, the map m -> C_K(m) is a pseudo-random permutation; under a fixed message block m, the map K -> C_K(m) is a pseudo-random function.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Key expansion is one of the two sources of T gates in the design of AES, and hence might have a strong impact on the overall efficiency of the circuit.”
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: fails — The paper may give no reason why it holds.
Probably not a substantial claim. The paper may give no reason why it holds.
In the paper
“Maximov's circuit has a much lower depth, but it only reduces the total depth, does not reduce the T-depth (which is already 0) and comes at the cost of an increased width.”
What the sources say
- Not matchedcites Max19
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Not matched
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“If rn < k , then K is almost certainly not unique. Even rn = k -3 gives less than a 1% chance of a unique key.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: Under a fixed key K, the map m -> C_K(m) is a pseudo-random permutation; under a fixed message block m, the map K -> C_K(m) is a pseudo-random function.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“For AES-128, 192 and 256 this implies minimum depths of 2 40 . 2 c s , 2 56 . 2 c s and 2 72 . 3 c s , respectively.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“While their method is based on the one in [GLRS16] using ancilla qubits for the round keys, our approach works completely in place and reduces width and depth at the same time.”
What the sources say
- Not matchedcites LPS19
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites GLRS16
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Not matched
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“While for AES-128 and AES-192, G D G W is smaller for the in-place implementation, G 2 D G W is smaller for Maximov's circuit.”
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“The S-box is the only source of T gates in a quantum circuit of AES.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: fails — The paper may give no reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. The paper may give no reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The explicit computation of the probabilities in Equation (1) shows that it using r = 2 for AES-128, r = 2 for AES-192 and r = 3 for AES-256 will guarantee a unique key with overwhelming probability. The probabilities that there are no spurious keys are 1 -ϵ , where ϵ < 2 -128 , ϵ < 2 -64 and ϵ < 2 -128 , respectively.”
boosteddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“For example, LowMC L1 can be broken with an attack having G -cost 1 . 25 · 2 123 in depth MAXDEPTH = 2 40 , while the original NIST bound in category 1 requires a scheme to not be broken by an attack using less than 2 130 gates.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The same holds for the DW -cost as we increase the width by factors less than 4 and simultaneously reduce the depth by more than that.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Note that AES-128 under MAXDEPTH = 2 96 is a special case as the attack does not require any parallelization and its cost is underestimated by the approximation.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: fails — The paper may give no reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. The paper may give no reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Costing the T depth of the resulting dummy AES operation returns the expected value of 2 × # of rounds × d , where d is the depth of the dummy S-box.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“We also note that the compiler is currently unable to optimize a given circuit by, e.g., searching through small circuit variations that may result in functionally the same operation at a smaller cost (say by allowing better use of the circuit area).”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“The AND and Toffoli gate designs we chose use measurements, hence CNOT, 1-qubit Clifford, measurement and depth counts are probabilistic.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“| LowMC L5 | 5070324 | 14274 | 15960 | 0 | 76 | 693471 | 1915 |”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“| LowMC L3 | 2271870 | 9398 | 12600 | 0 | 60 | 319317 | 1483 |”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“For the Q# simulator to run, we are required to use the Microsoft QDK standard library's Toffoli gate for evaluating both Toffoli and AND gates, which results in deeper than necessary circuits.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“We also have to explicitly SWAP values across wires, which costs 3 CNOT gates, rather than simply keeping track of the necessary free rewiring.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“| LowMC L1 | 689944 | 4932 | 8400 | 0 | 40 | 98699 | 991 |”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The explicit computation of the probabilities in Equation (1) shows that it using r = 2 for AES-128, r = 2 for AES-192 and r = 3 for AES-256 will guarantee a unique key with overwhelming probability. The probabilities that there are no spurious keys are 1 -ϵ , where ϵ < 2 -128 , ϵ < 2 -64 and ϵ < 2 -128 , respectively.”
boosteddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The explicit computation of the probabilities in Equation (1) shows that it using r = 2 for AES-128, r = 2 for AES-192 and r = 3 for AES-256 will guarantee a unique key with overwhelming probability. The probabilities that there are no spurious keys are 1 -ϵ , where ϵ < 2 -128 , ϵ < 2 -64 and ϵ < 2 -128 , respectively.”
boosteddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“a simple in-place implementation with depth 5 (T-depth 3) is shown in Figure 5, alongside a T-depth 1 out-of-place circuit, both of which were produced manually.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Even without parallelization, more than 2 pairs are never required for AES-128 and AES-192. The same holds for 4 or more pairs for AES-256.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“We note that the in-place design does require ancilla qubits as part of the concrete CCNOT implementation.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“The Q# Toffoli simulator does not currently support PRNG seeding for de-randomizing the measurements, 8 which means that estimating differently sized circuits with the same or similar depth (or re-estimating the same circuit multiple times) may result in slightly different numbers.”
hedgedconditional- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Note that AES-128 under MAXDEPTH = 2 96 is a special case as the attack does not require any parallelization and its cost is underestimated by the approximation.”
plaindirectSingle case- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Grover's algorithm does not parallelize well, meaning that minimizing depth rather than width is crucial to make the most out of the available depth.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
- The authors state this as an assumption: MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
In the paper
“Previous work in the specific case of AES derived the full gate cost by analyzing quantum circuits for the cipher, but focused on minimizing the number of qubits.”
What the sources say
- Not matchedcites [GLRS16]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. It may state two separate claims as one.
- Not matched
In the paper
“ShiftRow is a permutation on the full 128-bit AES state, happening across its four words [DR99, § 4.2.2]. As a permutation of qubits, it can be entirely encoded as rewiring.”
What the sources say
- Not matchedcites DR99
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Not matched
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The total distance any signal must travel is proportional to the square root of the size of this tree, i.e. √ S .”
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: fails — The paper may give no reason why it holds.
Probably not a substantial claim. The paper may give no reason why it holds.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“It follows that for two oracle circuits G and F , the total G -cost is lower for G if and only if G D G G < F D F G . That is, we wish to minimize the product G D G G .”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
In the paper
“Zalka [Zal99] concludes that in both cases, one only obtains a factor S gain in the number of Grover iterations when working with S parallel Grover oracles, and that this is asymptotically optimal.”
What the sources say
- Not matchedcites [Zal99]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
boosteddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
- The authors state this as an assumption: MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
- Not matched
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“It holds that p/c p < 1 . 45, so ( pC/ ( c p G G )) 2 < 2 . 11 and for p = 1, we have ( pC/ ( c p G G )) 2 = 16 /π 2 · C 2 / G 2 G ≈ 1 . 62 · C 2 / G 2 G ≤ 1 . 62.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: unclear — It is unclear why the paper says it holds.
It may state two separate claims as one.
None of the sources cited for this claim have been checked yet.
In the paper
“The lower- and upper-triangular components L and U of the decomposition can be implemented as described above by using the appropriate CNOT gates, while the final permutation P does not require any quantum gates and instead, is realized by appropriately keeping track of the necessary rewiring.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
In the paper
“Another advantage of inner parallelization is that dividing the search space separates any spurious keys into different subsets and reduces the search problem to finding a unique key. This allows us to reduce the number r of message blocks in the Grover oracle and was already observed by Kim, Han, and Jeong [KHJ18] in the context of measure-and-repeat methods.”
What the sources say
- Not matchedcites [KHJ18]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
- The authors state this as an assumption: MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
- Not matched
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Hence, § 2.3 indicates that when optimizing the DW -cost metric with depth restriction, Maximov's circuit should be preferred. If there is no depth restriction, though, the in-place design leads to a lower DW -cost.”
hedgeddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
In the paper
“All quantum circuits for AES and LowMC described in this paper were designed, tested, and costed in the Q# programming language [SGT + 18], which supports all assumptions discussed here.”
What the sources say
- Not matchedcites [SGT + 18]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
- The authors state this as an assumption: Full parallelism holds: a quantum circuit can apply any number of gates simultaneously so long as these gates act on disjoint sets of qubits.
- Not matched
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“In general, high parallelization makes spurious keys irrelevant, and the Grover oracle can simply use the smallest r such that SKP( k, n, r, S ) is still small enough, i.e. less than a desired bound.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
- The authors state this as an assumption: MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
- The authors state this as an assumption: The overall attack strategy is guaranteed to return a solution with high probability close to 1 within the given depth bound.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Similarly, RotByte is a circular left shift of a word by 8 bits, and can be implemented by appropriate rewiring as well.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. It may state two separate claims as one.
In the paper
“Kim et al. [KHJ18, Equation (7)] describe the success probability after a certain number of Grover iterations when the number of spurious keys is unknown. The optimal number of iterations gives a maximum success probability of 0 . 556, making it likely that the first attempt will not find the correct key and one must repeat the algorithm.”
What the sources say
- Not matchedcites [KHJ18]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Not matched
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“This 'dummy' AES design had the expected T-depth of 2 n · d . Thus we believe the Q# compiler found non-trivial parallelization between components of the S-box and the surrounding circuit.”
hedgeddirectSingle case- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
None of the sources cited for this claim have been checked yet.
In the paper
“AddRoundKey performs a bitwise XOR of a round key to the internal AES state and can be realized with a parallel application of 128 CNOT gates, controlled on the round key qubits and targeted on the state qubits.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“In the case of LowMC inside of Picnic, the full S-boxLayer consists of 10 parallel S-boxes run on the 30 low order bits of the state.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
In the paper
“This results in a sub-optimal circuit, which can clearly be improved by porting the more recent version from [DKP + 19] instead.”
What the sources say
- Not matchedcites DKP+19
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
boosteddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Not matched
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Again, for Picnic, just like the matrices used in the LinearLayer transformation, all KM i are invertible. Hence, we can use a PLU decomposition again.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
What the paper did — it cites no source for this, so there is none to check. The quote shows it is in the paper.
In the paper
“Our results for each specific setting incorporate the reduction of plaintext-ciphertext pairs through parallelization, provide the correct cost if parallelization is not necessary and use improved circuit designs.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“In particular, Picnic proposes three parameter sets, with (key size , block size) ∈ { (128 , 128) , (192 , 192) , (256 , 256) } .”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The above formula does not take into account that parallelization often allows us to reduce the number of required plaintext-ciphertext pairs, resulting in a G -cost reduction for search in each parallel Grover instance by a factor larger than x .”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: fails — The paper may give no reason why it holds.
Probably not a substantial claim. The paper may give no reason why it holds.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“In Picnic, for every round and every parameter set, all LinearLayer matrices are invertible (due to LowMC's specification requirements), and hence the matrix multiplication can be implemented via a PLU decomposition.”
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
In the paper
“If one is content with a success probability lower than 1, it suffices to use r = ⌈ k/n ⌉ blocks of plaintext-ciphertext pairs. In this case, it is enough to use r = 1 for AES-128, r = 2 for AES-192 and r = 2 for AES-256.”
What the sources say
- Not matchedcites LPS19
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Not matched
The authors state this as an assumption.
Under a fixed key K, the map m -> C_K(m) is a pseudo-random permutation; under a fixed message block m, the map K -> C_K(m) is a pseudo-random function.
“We assume that under a fixed key K , the map { 0 , 1 } n →{ 0 , 1 } n , m ↦→ C K ( m ) is a pseudo-random permutation; and under a fixed message block m , the map { 0 , 1 } k → { 0 , 1 } n , K ↦→ C K ( m ) is a pseudo-random function.”
The authors state this as an assumption.
Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
“In this work, we assume that any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.”
The authors state this as an assumption.
MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.
“We do assume that MAXDEPTH constitutes a hard upper bound on the total depth of a quantum attack, including possible repetitions of a Grover instance.”
The authors state this as an assumption.
The overall attack strategy is guaranteed to return a solution with high probability close to 1 within the given depth bound.
“We consider it reasonable to expect that the overall attack strategy is guaranteed to return a solution with high probability close to 1 within the given depth bound.”
The authors state this as an assumption.
Full parallelism holds: a quantum circuit can apply any number of gates simultaneously so long as these gates act on disjoint sets of qubits.
“We make the standard assumption of full parallelism , meaning that a quantum circuit can apply any number of gates simultaneously so long as these gates act on disjoint sets of qubits [BBG + 13,GR03].”
The authors state this as an assumption.
Layout and communication costs for the Grover oracle circuit are ignored.
“We ignore all concerns of layout and communication costs for the Grover oracle circuit.”
The authors state this as an assumption.
Parallelization of Grover's algorithm uses inner parallelization via splitting up the search space.
“This necessarily means that we must include parallelization, which we assume to use inner parallelization via splitting up the search space, see § 2.3.”
“Imposing a depth limit forces the parallelization of Grover's algorithm, which we assume uses inner parallelization, see § 2.3.”
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830 · cited 3×
“The only caveat thus far is a security reduction due to key search or pre-image attacks with Grover’s algorithm [22].”
BackgroundMethodAlgorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Trefethen, L. N., & Bau, III (1997) · doi:10.1137/1.9780898719574 · Cited by 3,301
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059
Trefethen, L. N., & Bau, D. (2008) · Choice Reviews Online · doi:10.5860/choice.45-5628 · Cited by 2,784
(1996) · Cited by 824
A Compact Rijndael Hardware Architecture with S-Box Optimization
Satoh, A., Morioka, S., Takano, K., & Munetoh, S. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45682-1_15 · Cited by 685
A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases
Itoh, T., & Tsujii, S. (1988) · Information and Computation · doi:10.1016/0890-5401(88)90024-7 · Cited by 635
Grover’s quantum searching algorithm is optimal
Zalka, C. (1999) · Physical Review A · doi:10.1103/physreva.60.2746 · Cited by 635
Cited by
Sorted by citations
Items 101–200 of 234
Quantum circuit for implementing Camellia S-box with low costs
Li, Z., Fei, G., Su-Juan, Q., & Qiao-yan, W. (2023) · Zhongguo kexue. Wulixue Lixue Tianwenxue · doi:10.1360/sspma-2022-0485 · Cited by 7
Saarinen, M.-J. O., Newell, G. R., & Marshall, B. (2020) · doi:10.1145/3411504.3421212 · Cited by 7
“As an example, the original Intel RNG [30], whose output generation is based on AES-128 can be attacked using Grover’s algorithm with approximately square-root effort [21].”
MethodFrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism
Glabush, L., Longa, P., Naehrig, M., Peikert, C., Stebila, D., & Virdia, F. (2025) · IACR Communications in Cryptology · doi:10.62056/ayivom2hd · Cited by 9
Self-citationQuantum security analysis of Rocca
Anand, R., & Isobe, T. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-03908-3 · Cited by 5
“In recent times there has been an a lot of research in optimizing the quantum circuit of AES [1, 15, 19, 21, 26, 33, 47], all improving on the previous results.”
BackgroundResultAnalysis of Atom against quantum attacks
Anand, R., Nandi, R., & Isobe, T. (2023) · IET Quantum Communication · doi:10.1049/qtc2.12076 · Cited by 6
Quantum Implementation of AIM: Aiming for Low-Depth
Jang, K., Oh, Y., Kim, H., & Seo, H. (2024) · Applied Sciences · doi:10.3390/app14072824 · Cited by 5
Mixed Grover: A Hybrid Version to Improve Grover's Algorithm for Unstructured Database Search
Piron, R., Habibie, M. I., & Goursaud, C. (2025) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2025.3555562 · Cited by 5
“For instance, Grover’s algorithm has already been applied to the graph coloring problem [8], [9] and AES key search [10].”
Quantum algorithms for the Goldreich–Levin learning problem
Li, H. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02839-7 · Cited by 4
Gheorghe-Pop, I.-D., Tcholtchev, N., Ritter, T., & Hauswirth, M. (2021) · Lecture notes in networks and systems · doi:10.1007/978-3-030-80119-9_9 · Cited by 4
Research on Enterprise Financial Accounting Information Security Model Based on Big Data
Zhong, R., Zhang, Q., & Zhao, Y. (2022) · Wireless Communications and Mobile Computing · doi:10.1155/2022/7929846 · Cited by 4
“Therefore, this study improves the S-box of AES [22].”
BackgroundHybrid Decoding – Classical-Quantum Trade-Offs for Information Set Decoding
Esser, A., Ramos-Calderer, S., Bellini, E., Latorre, J. I., & Manzano, M. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-17234-2_1 · Cited by 4
“The idea of such classical co-processors has mostly been used to parallelize quantum circuits or instantiate circuits under depth constraints, e.g. when analyzing the quantum security of schemes under the MAXDEPTH constraint specified by NIST [2, 6, 7, 14, 18].”
MethodEfficient quantum circuit implementation of the SM4 S-box
JiaHong, L., Tan, X., Ming, L., & DaiPengWei, B. (2023) · Zhongguo kexue. Wulixue Lixue Tianwenxue · doi:10.1360/sspma-2023-0386 · Cited by 4
Development of the RISC-V entropy source interface
Saarinen, M.-J. O., Newell, G. R., & Marshall, B. (2022) · Journal of Cryptographic Engineering · doi:10.1007/s13389-021-00275-6 · Cited by 4
“As an example, the original Intel RNG [33], whose output generation is based on AES-128, can be attacked using Grover’s algorithm with approximately square-root effort [23].”
MethodLowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic NetworksPreprint
Häner, T., & Soeken, M. (2020) · arXiv.org · doi:10.48550/arxiv.2006.03845 · Cited by 11
“The corresponding 104 Jaques, Naehrig, Roetteler, Virdia [22] Amy, Matteo, Gheorghiu, Mosca, Parent, Schanck [3] Haener, Soeken, Roetteler, Svore [19] This work Figure 3: These plots contain various resource estimates that can be found in the literature, together with all Pareto-optimal results for…”
BackgroundIn-place implementation of Quantum-GimliPreprint
Schlieper, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.06319 · Cited by 4
“Recently there have been many results concerning Grover attacks on symmetric ciphers, especially on lightweight ciphers and related implementations and resource estimates of the quantum implementation of the ciphers and attacks [2,5,7,8,12], as well as attempts to adapt classical attacks into the quantum setting [6,10…”
BackgroundMethodDedicated Quantum Attacks on XOR-Type Function With Applications to Beyond-Birthday- Bound MACs
Shi, T., Wu, W., Hu, B., Guan, J., Sui, H., Wang, S., & Zhang, M. (2024) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3402970 · Cited by 3
“However, at this point, the success probability is not guaranteed to be closed to 1 [24], shown as follows : In addition, each instance costs κ + W test qubits, making S instances use a total of (κ + W test ) S qubits.”
BackgroundMethodInfluentialQuantum implementation of SLIM and its Grover cryptanalysis
Cildiroglu, H. O., & Yayla, O. (2025) · Physica Scripta · doi:10.1088/1402-4896/ae1336 · Cited by 3
New Results in Quantum Analysis of LED: Featuring One and Two Oracle Attacks
Wang, S., Jang, K., Baksi, A., Chakraborty, S., Lee, B., Chattopadhyay, A., & Seo, H. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-13301-4_15 · Cited by 3
Quantum circuit for implementing AES S-box with low costs
Chen, H.-N., Cai, B., Gao, F., & Lin, S. (2026) · Quantum Information Processing · doi:10.1007/s11128-026-05083-7 · Cited by 5
A new post-quantum voting protocol based on physical laws
Sun, Z., Gao, W., Dong, H., Xie, H., & Yang, L. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03628-0 · Cited by 3
“In addition, there are also many other studies that use quantum algorithms to analyse attacks on classic block cipher [18, 28, 29].”
BackgroundYang, Y., Jang, K., Kim, H., Song, G., & Seo, H. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-25659-2_4 · Cited by 3
Bhattacharya, P., & Verma, A. (2025) · Elsevier eBooks · doi:10.1016/b978-0-443-29654-3.00012-0 · Cited by 3
Quantum Computing: Threat to Cybersecurity
Pal, D., & Sau, D. (2025) · Springer eBooks · doi:10.1007/978-981-96-4948-8_7 · Cited by 3
On Forging SPHINCS$$^{+}$$-Haraka Signatures on a Fault-Tolerant Quantum Computer
Berger, R., & Tiepelt, M. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-88238-9_3 · Cited by 4
A Note on Quantum Collision Resistance of Double-Block-Length Compression Functions
Hirose, S., & Kuwakado, H. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-92641-0_8 · Cited by 3
Quantum partial search algorithm with smaller oracles for multiple target items
Li, D., Qian, L., Zhou, Y., et al. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03496-8 · Cited by 3
$$T{-}depth$$ Reduction Method for Efficient $$SHA{-}256$$ Quantum Circuit Construction
Lee, J., Lee, S., Lee, Y.-S., & Choi, D. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-08896-4_20 · Cited by 3
Practical Usage of Radical Isogenies for CSIDH
Heo, D., Kim, S., & Hong, S. (2023) · IEEE Access · doi:10.1109/access.2023.3272549 · Cited by 3
“Then, the x coordinates of their sum P + Q , denoted as x p + q , and the doubling of [2] P , denoted as x [2] P , can be computed as follows : x p + q = ( x p x q − 1) 2 / ( x p − q ( x p − x q ) 2 ) We can induce a similar formula for a Montgomery curve, M a [22].”
MethodConcrete Analysis of Quantum Lattice Enumeration
Bai, S., van Hoof, M.-I., Johnson, F. B., Lange, T., & Ngo, T. (2023) · Lecture notes in computer science · doi:10.1007/978-981-99-8727-6_5 · Cited by 4
An efficient quantum circuit implementation of ZUC-128 cipher with low T-depth
Jian, Z., SiMing, X., ChangZhong, Z., & Wu, W. (2024) · Zhongguo kexue. Wulixue Lixue Tianwenxue · doi:10.1360/sspma-2024-0147 · Cited by 3
Quantum resource estimation of PRINCE and Midori Block Ciphers
Akhlaq, A. H., Allu, S. N., & Yerukala, N. (2024) · International Journal of Information Technology · doi:10.1007/s41870-024-01997-6 · Cited by 3
“In [13] the quantum key search attacks are explained under a depth restriction and new techniques that reduce the oracle depth have been introduced, even if it requires more qubits.”
Quantum Truncated Differential and Boomerang Attack
Xie, H., & Yang, L. (2024) · Symmetry · doi:10.3390/sym16091124 · Cited by 3
Quantum Procedures for Nested Search Problems
Schrottenloher, A., & Stevens, M. (2024) · IACR Communications in Cryptology · doi:10.62056/aee0fhbmo · Cited by 5
Grover on Caesar and Vigenère Ciphers.Preprint
Song, G., Jang, K., Kim, H., et al. (2021) · IACR Cryptology ePrint Archive · Cited by 3
A Novel Framework to Construct Quantum Circuits of S-Boxes: Applications to 4-bit S-boxesPreprint
Jeon, Y., Baek, S., & Kim, J. (2023) · Research Square · doi:10.21203/rs.3.rs-2727191/v1 · Cited by 3
Quantum Attacks on MIBS Block Cipher Based on Bernstein–Vazirani Algorithm
Xie, H., Zhao, Z., Wang, K., et al. (2024) · Mathematics · doi:10.3390/math12172678 · Cited by 2
Constructing resource-efficient quantum circuits for AES
Jiang, L.-L., Cai, B.-B., Gao, F., Qin, S.-J., Jin, Z.-P., & Wen, Q.-Y. (2025) · Frontiers of Physics · doi:10.3389/fphy.2025.1582819 · Cited by 4
Quantum Circuit Design for Finding k-Cliques via Quantum Amplitude Amplification Strategies
Perriello, S. (2025) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/3719276.3725200 · Cited by 2
“A C 2 NOT gate can be implemented with T -depth 1 and T -size 4 using one auxiliary qubit [19].”
Conditional Constant Function Problem and Its Quantum Solutions: Attacking Feistel Ciphers
Li, Z., Fan, S., Gao, F., Hao, Y., Hu, X.-C., Wan, L., Sun, H.-W., & Su, Q. (2025) · IEEE Internet of Things Journal · doi:10.1109/jiot.2025.3627427 · Cited by 2
“In this article, we apply a Cli ff ord + T implementation of QAND from [35], which requires four qubits, 15 Cli ff ord + T gates, and a depth of 8.”
Differential Cryptanalysis of Block Ciphers Through the Lens of Symmetry: A Review
Zhang, L., Wu, Y., Wen, Y., et al. (2025) · Symmetry · doi:10.3390/sym18010008 · Cited by 2
Optimal T-depth Quantum Circuits for Implementing Arbitrary Boolean Functions
Dutta, S., Bhaumik, A., Chattopadhyay, A., & Maitra, S. (2025) · Quantum Information & Computation · doi:10.2478/qic-2025-0032 · Cited by 3
“[13] (see Figure 1b), the Clifford+T decomposition of an n -MCT gate, implemented via Clifford plus Toffoli decomposition, is lower bounded by ⌈ log 2 n ⌉ , requiring 2 n − 2 additional ancilla qubits and 4 n − 4 T gates.”
InfluentialAdvanced Encryption Standard on a Quantum System
Dhanapal, A. D., Ramanujan, S. A., & Jeyalakshmi, V. (2023) · International Conference on Integrated Intelligence and Communication Systems (ICIICS) · doi:10.1109/iciics59993.2023.10421474 · Cited by 2
“For example, the emergence of Grover’s Search in 1996 made it easier to perform key recovery attacks on symmetric key ciphers as shown by [13] and [14].”
Wu, H.-Y., Feng, X., & Zhang, J.-L. (2024) · Entropy · doi:10.3390/e26030216 · Cited by 2
“For a meaningful definition of the security categories, NIST derives security I ∼ V from the gate and depth cost estimates for a brute-force attack on the AES algorithm by Jaques et al. [17].”
BackgroundMethodDepth-Optimized Quantum Implementation of ARIA
Yang, Y., Jang, K., Oh, Y., & Seo, H. (2023) · IACR Cryptology ePrint Archive · doi:10.1007/978-981-97-1235-9_5 · Cited by 1
“…circuits to reduce Grover’s key search costs, NIST has defined the costs for Levels 1, 3, and 5 as 2 157 , 2 221 , and 2 285 , respectively in their recent document [18] by citing the costs of depth-optimized quantum circuit implementations for AES [13] presented by Jaques et al. at Eurocrypt’20.”
BackgroundMethodInfluentialEnhanced QSimon Algorithm for Attacking the Offset Two‐Round Scheme
Wu, H., Feng, X., Zhang, K., et al. (2024) · Advanced Quantum Technologies · doi:10.1002/qute.202300384 · Cited by 2
Hybrid QKD Approach for Multi-User Quantum Networks: Practical Concept
Begimbayeva, Y., Zhaxalykov, T., Makarov, M. V., et al. (2024) · doi:10.1109/opcs63516.2024.10720438 · Cited by 2
“In addition to this, the current progress and roadmap of tech giants such as IBM [2] promises rapid development in the computing power of quantum computers, thereby threatening existing secure communication protocols such as RSA [3] and AES [4].”
BackgroundA survey of the research on quantum circuit synthesis and optimization of symmetric-key cryptography
Da, L., Fei, G., Jian, Z., Huang, Z., Sun, S., & Bing, S. (2024) · Zhongguo kexue. Wulixue Lixue Tianwenxue · doi:10.1360/sspma-2024-0433 · Cited by 2
Nagata, K., Wong, R., Diep, D. N., & Nakamura, T. (2023) · Quantum Studies Mathematics and Foundations · doi:10.1007/s40509-023-00294-4 · Cited by 2
“The algorithm attacks block ciphers by searching for a key that matches a small number of plaintext–ciphertext pairs and requires O( √ N ) calls to the cipher [3].”
BackgroundQuantum‐Resistant Cryptography
Grimes, R. A. (2019) · Wiley eBooks · doi:10.1002/9781119618232.ch6 · Cited by 2
Improving post-quantum cryptography through cryptanalysis
Schanck, J. M. (2020) · UWSpace (University of Waterloo) · Cited by 2
Grover on GIFT.Preprint
Jang, K., Kim, H., Eum, S., & Seo, H. (2020) · IACR Cryptology ePrint Archive · Cited by 2
Circuit implementation of the globally optimized HHL algorithm and experiments on qiskitPreprint
Zhang, M., Dong, L., Zeng, Y., & Cao, N. (2022) · Research Square · doi:10.21203/rs.3.rs-1505699/v1 · Cited by 2
Quantum implementaion of SM4 block cipher with less qubitsPreprint
Luo, Q.-B., Li, Q., Li, X., Yang, G., Shen, J., & Zheng, M. (2023) · Research Square · doi:10.21203/rs.3.rs-3105531/v1 · Cited by 2
Post‐Quantum Symmetric Cryptography
Naya‐Plasencia, M. (2023) · doi:10.1002/9781394256327.ch17 · Cited by 2
Layout-Aware Quantum Circuitry and Algorithmic Extensions to Grover's Algorithm
Al-Bayaty, A. (2025) · doi:10.15760/etd.3924 · Cited by 2
A Resource Estimation and Verification Workflow in Q# Special session paper
Soeken, M., Mykhailova, M., Kliuchnikov, V., Granade, C., & Vaschillo, A. (2021) · Design, Automation, and Test in Europe · doi:10.23919/date51398.2021.9474228 · Cited by 1
“We refer the user to [12], [30], [31], [32] for further details and pointers to the Q# code used in their projects.”
MethodFinding Shortest Vector Using Quantum NV Sieve on Grover
Kim, H., Jang, K., Oh, Y., et al. (2024) · Lecture notes in computer science · doi:10.1007/978-981-97-1235-9_6 · Cited by 1
“The diffusion operator has a fixed implementation method and is often excluded from resource estimation [5,18] because the overhead is so small that it is negligible.”
Quantum Implementation and Analysis of ARIA
Oh, Y., Jang, K., Yang, Y., & Seo, H. (2024) · Silicon Valley Cybersecurity Conference · doi:10.1109/svcc61185.2024.10637311 · Cited by 1
“In [8], [17], it was proposed that obtaining r = ⌈ key size/block size ⌉ pairs of plaintext-ciphertext is adequate to identify a unique key.”
BackgroundMethodInfluentialLi, A., Xia, Q., Zhu, Q., & Yang, L. (2024) · Cybersecurity · doi:10.1186/s42400-024-00257-1 · Cited by 1
“This has been analyzed through perspectives such as the gate operation rate (Yang and Zhou 2013; Sun et al. 2022), quantum resources (Grassl et al. 2016; Langenberg et al. 2020; Jaques et al. 2020; Huang et al. 2022), and the required storage space for algorithms (Chailloux et al. 2017).”
Bakharev, A. O. (2024) · Journal of Applied and Industrial Mathematics · doi:10.1134/s1990478924030037 · Cited by 1
A Quantum Circuit to Execute a Key-Recovery Attack Against the DES and 3DES Block Ciphers
Perriello, S., Barenghi, A., & Pelosi, G. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00011 · Cited by 1
Post-Quantum Migration of the Tor Application
Berger, D., Lemoudden, M., & Buchanan, W. J. (2025) · Journal of Cybersecurity and Privacy · doi:10.3390/jcp5020013 · Cited by 1
“Since Grover’s algorithm [2] demonstrates limited paral-lelisation capabilities, the quantum threat is not estimated to be significant to asymmetric cryptosystems; thus, increasing the key size is expected to provide sufficient security [17].”
Chakraborty, S., Islam, S. H., & Baksi, A. (2025) · Computers & electrical engineering · doi:10.1016/j.compeleceng.2025.110370 · Cited by 2
New quantum attacks on some Feistel variants
Lan, Q., Zou, J. X., & Wei, J. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04852-0 · Cited by 1
Quantum Cryptanalysis of Symmetric-Key Ciphers: Background and Challenges
Pal, D., Baksi, A., & Ganguly, A. (2025) · Springer eBooks · doi:10.1007/978-981-96-4948-8_9 · Cited by 1
On the construction of quantum circuits for S-boxes with different criteria based on the SAT solver
Lin, D., Yang, C., Xu, S., Tian, S., & Sun, B. (2026) · Quantum Information Processing · doi:10.1007/s11128-025-05049-1 · Cited by 1
CKGS: A Way Of Compressed Key Guessing Space to Reduce Ghost Peaks
Li, D., Li, L., & Ou, Y. (2022) · KSII Transactions on Internet and Information Systems · doi:10.3837/tiis.2022.03.016 · Cited by 1
Bakharev, A. O. (2023) · Journal of Applied and Industrial Mathematics · doi:10.1134/s1990478923030018 · Cited by 1
Quantum Collision Resistance of Double-Block-Length Hashing
Hirose, S., & KUWAKADO, H. (2024) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.2023dmp0007 · Cited by 1
“A Grover oracle of the collision attack is also presented, which is similar to that of the quantum exhaustive key search of a block cipher [12], [13].”
MethodOptimized Quantum Implementation of SEED
Oh, Y., Jang, K., Yang, Y., & Seo, H. (2024) · Lecture notes in computer science · doi:10.1007/978-981-97-1235-9_4 · Cited by 1
“Based on these NIST criteria, continuous efforts have been made to estimate the complexity of Grover’s key search for symmetric-key ciphers and evaluate post-quantum security [5,6,7].”
Depth–measurement trade-off for quantum search on block ciphers
Ng, W.-J., & Tan, C. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04359-0 · Cited by 1
“In [16], the authors recommend using w = kn plaintext–ciphertext pairs to find the secret key with overwhelming probability.”
InfluentialQuantum rectangular MinRank attack on multi-layer UOV signature schemes
Cho, S.-M., & Seo, S.-H. (2024) · Scientific Reports · doi:10.1038/s41598-024-66841-0 · Cited by 1
“This criterion was revised in 2022 for the additional digital signature standardization project 18 to reflect the quantum resource estimates of the improved Grover’s algorithm by S. Jaques et al. in 2020 19 .”
Zhang, K., Shang, T., Tang, Y., & Liu, J. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04491-x · Cited by 1
“Jaques et al. [10] studied the quantum computational complexity of attacking advanced encryption standard (AES) based on Grover’s algorithm and obtained better query complexity.”
Depth Optimized Quantum Circuits for HIGHT and LEA
Jang, K., Oh, Y., Lee, M., Kim, D., & Seo, H. (2024) · Silicon Valley Cybersecurity Conference (SVCC) · doi:10.1109/svcc61185.2024.10637378 · Cited by 1
“Since the complexity of the diffusion operator is negligible compared to the quantum circuit of the target cipher, it is commonly omitted in estimations [15], [16].”
BackgroundMethodResultInfluentialDemonstration of Grover’s algorithm for retrieving secret keys in a basic SPN block cipher
Vu, M. T., Nguyen, V. N., Le, Q. D., & Do, Q. T. (2024) · CTU Journal of Innovation and Sustainable Development · doi:10.22144/ctujoisd.2024.317 · Cited by 1
“In recent years, there have been many publications on applying Grover's algorithm to find cryptographic keys (Grassl et al., 2016; Kim et al., 2018; Denisenko, 2019; Jaques et al., 2020).”
MethodPhysical Qubits Estimation for Quantum S-Box
Lee, Y.-S., Lee, J., Chung, B., & Kang, Y. (2024) · Information and Communication Technology Convergence · doi:10.1109/ictc62082.2024.10826924 · Cited by 1
“Liu's circuit offers advantages over Huang’s quantum S-box in terms of DW-cost, which is calculated as the product of the circuit's depth and width [8].”
Oh, Y., Jang, K., & Seo, H. (2025) · Lecture notes in computer science · doi:10.1007/978-981-96-1624-4_27 · Cited by 1
“Notably, extensive research has been conducted on Grover’s algorithm for block ciphers and hash functions [8,10,13].”
BackgroundQuantum circuit implementation and security analysis of IVLBC
Ding, L., Luo, Q.-B., Lv, Y., Zheng, Y., Liao, H., & Chen, Z. (2025) · Classical and Quantum Gravity · doi:10.1088/1361-6382/adc6eb · Cited by 1
“Driven by this research trend, Jaques et al [12] proposed a more compact quantum circuit for the AES block cipher, aiming to reduce the resource consumption and cost associated with implementing quantum attacks.”
Liao, H., Luo, Q.-B., Zheng, Y., et al. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04749-y · Cited by 1
“Due to the lack of specific numerical values for SWAP operations in the cryptography community [29– 32] and related research on binary field multiplication, we do not include it in the cost comparison.”
Optimized quantum folding Barrett reduction for quantum modular multipliers
Zhang, J., Cho, S.-M., Lee, C., & Seo, S.-H. (2025) · Scientific Reports · doi:10.1038/s41598-025-04987-1 · Cited by 1
A Quantum Differential Attack on ChaCha and Related Resources Estimation
Mandal, M., Garai, H. K., & Dey, S. (2025) · IEEE Access · doi:10.1109/access.2025.3593658 · Cited by 1
“This quantum speed-up has spurred substantial research into quantum cryptanalysis, particularly on key recovery attacks against prominent block ciphers like AES [6], [7], [8], [9], as well as lightweight ciphers such as Simon [10] and Speck [11].”
An Economic Model for Quantum Key-Recovery Attacks against Ideal CiphersPreprint
Harsha, B., & Blocki, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.05911 · Cited by 1
“In recent (concurrent) work [27] shows improvements similar to this example, which would allow attacks with this cost to be run in the 100 year quantum mania scenario.”
BackgroundQuantum Key Recovery Attack on SIMON Block CipherPreprint
Liu, H., & Yang, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.08321
“When computing the depth of a quantum circuit, we also adopt the full parallelism assumption as in [24], which means a quantum circuit can apply any number of gates simultaneously so long as these gates act on disjoint sets of qubits.”
BackgroundMethodParallelism strategies for the tuneable golden-claw finding problem
Azarderakhsh, R., Biasse, J., Khatib, R. E., Langenberg, B., & Pring, B. (2021) · International Journal of Computer Mathematics Computer Systems Theory · doi:10.1080/23799927.2021.1884605
“…synthesized using the Clifford + T universal quantum gate set [31] and we use a simple construction for ∧ m ( X ) built from quantum AND gates [20,28] that requires a quantum circuit-size of O ( m ) and quantum circuit-depth of O ( log 2 m ) Clifford + T gates if we use O ( m ) clean ancilla…”
BackgroundMethodConclusion and Research Direction
Sapv, T., Bera, D., Maitra, A., et al. (2021) · SpringerBriefs in computer science · doi:10.1007/978-981-16-3061-3_5
OSKR/OKAI: Systematic Optimization of Key Encapsulation Mechanisms from Module LatticePreprint
Shen, S., He, F., Liang, Z., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2109.02893
“For example, the updated quantum analysis on AES [11] overall reduces the original estimate of quantum cost in bits against AES (specified in the call for proposals of NIST PQC standardization [21]) between 11 and 13, and this line of research is quite active now.”
BackgroundLinear Cryptanalysis through the Lens of Clauser-Horne-Shimony-Holt GamePreprint
Maitra, A., Anand, R., & Dutta, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.01656
Savoie, M. J. (1994) · Spectrum Research Repository (Concordia University)
Hoofnagle, C. J., & Garfinkel, S. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108883719.019
Hoofnagle, C. J., & Garfinkel, S. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108883719.016
Post-Quantum Logic LockingPreprint
Baehr, J., & Zeh, A. (2022) · doi:10.36227/techrxiv.20036924.v1
Post-Quantum Logic LockingPreprint
Baehr, J., & Zeh, A. (2022) · doi:10.36227/techrxiv.20036924
Quantum rebound attacks on reduced‐round ARIA‐based hash functions
Baek, S., & Kim, J. (2023) · ETRI Journal · doi:10.4218/etrij.2022-0032
“As there are half inverse S-boxes in the S-box layer of each round, we need ð 8 þ 8 (cid:2) 2 Þ(cid:2) 5 (cid:2) 2 (cid:2) ð 1 = 160 Þ ≈ 2 0 : 58 seven-round ARIA computations.”
BackgroundMethodInfluentialOn post-quantum security of symmetric cryptosystems
Hosoyamada, A. (2023) · IEICE ESS FUNDAMENTALS REVIEW · doi:10.1587/essfr.17.1_59
Quantum Computing Research Lines in the Italian Center for Supercomputing
Barenghi, A., Cremonesi, P., & Pelosi, G. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-46077-7_28
Grover on Chosen IV Related Key Attack Against GRAIN-128a
Maitra, A., Samanta, A., Kar, S., Garai, H. K., Mandal, M., & Dey, S. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-56232-7_14
The serial and/or parallel execution of Grover's algorithmPreprint
Creemers, S. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4889509
Quantum Automated Tools for Finding Impossible Differentials
Xie, H., Xia, Q., Wang, K., et al. (2024) · Mathematics · doi:10.3390/math12162598
G, D. M., Jopate, R., & Sundaravadivazhagan, B. (2025) · doi:10.1002/9781394242399.ch14
Quantum Quest: Resource Requirement of RC4 Cryptanalysis under Grover’s Lens
Sen, S., Bajpayee, S., Mukherjee, I., Paul, G., & Singh, B. (2024) · 2024 IEEE Calcutta Conference (CALCON) · doi:10.1109/calcon63337.2024.10914073
Metadata
- Authors
- Jaques, S., Naehrig, M., Roetteler, M., & Virdia, F.
- Affiliations
- University of Oxford (GB)
- Microsoft (United States) (US)
- Royal Holloway University of London (GB)
- Corresponding author
- Jaques, Samuel
- Naehrig, Michael
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer International Publishing
- Published
- 2020
- Pages
- 280-310
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W2979004593
- Semantic Scholar
- 9be5e82517599d59e5feca01221741b57e679cf6
- Cited by
- 234
- References
- 48
- Citations by year
- 2026: 27 · 2025: 36 · 2024: 47 · 2023: 38 · 2022: 33 · 2021: 31 · 2020: 19
- FWCI
- 11.54
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- Lecture notes in computer science (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Microsoft Research
- Government of the United Kingdom
- University of Oxford
- Engineering and Physical Sciences Research Council (EP/P009301/1)
- Royal Holloway, University of London (EP/P009301/1)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptographic Implementations and Security
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Keywords
- Grover's algorithm, AES, block cipher, quantum circuit design, circuit depth, gate count, post-quantum cryptography, picnics, quantum resource estimation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
A language model drew the claims from the paper on 2026-10-23, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-23 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
