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
Reducing the Cost of Implementing AES as a Quantum Circuit
Langenberg, B., Pham, H., & Steinwandt, R. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.2965697 · Cited by 85
“CNOT | (T[0], T[12]) CNOT | (T[3], T[12]) #t43”
BackgroundInfluentialModule-Lattice-Based Key-Encapsulation Mechanism Standard
(2023) · doi:10.6028/nist.fips.203.ipd · Cited by 106
RetractedOptimizing Implementations of Linear Layers
Xiang, Z., Zeng, X., Lin, D., et al. (2020) · IACR Transactions on Symmetric Cryptology · doi:10.46586/tosc.v2020.i2.120-145 · Cited by 88
Quantum Circuit Implementations of AES with Fewer Qubits
Zou, J. X., Wei, Z., Sun, S., Liu, X., & Wu, W. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-64834-3_24 · Cited by 80
“Due to the importance of AES, it is one of the most studied ciphers [11,17,3,18,15] in Corresponding author. the context of efficient synthesis of quantum circuits.”
BackgroundMethodModule-Lattice-Based Digital Signature Standard
(2023) · doi:10.6028/nist.fips.204.ipd · Cited by 90
Retracted
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
