Implementing Grover Oracles for Quantum Key Search on AES and LowMC

May combine two claims.

The paper releases 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 quantum resource estimates.

“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.”

The quote only partly states this claim.

The paper's circuits for AES and LowMC give a lower overall attack cost in both the gate count and depth-times-width cost models than previous circuits.

“Our circuits give a lower overall attack cost in both the gate count and depth-times-width cost models.”

• AssumptionThe authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
• AssumptionThe 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.

May combine two claims.

The paper's work results in the most shallow quantum implementation of AES proposed so far, and the first ever for LowMC.

“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.”

• AssumptionThe authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
• AssumptionThe 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.

May combine two claims.

The paper presents new, lower cost estimates for each NIST security category, with implications for the security assessment of post-quantum cryptography.

“We present new, lower cost estimates for each category, so our work has immediate implications for the security assessment of post-quantum cryptography.”

• cites [NIS16]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• AssumptionThe authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
• AssumptionThe 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.

May combine two claims.

The results obtained here differ from [LPS19, §3.2] due to difference in counting gates and depth: [LPS19] counts Toffoli gates, while the Q# resource estimator costs at a lower level of T gates and also counts all gates needed to implement a Toffoli gate.

“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.”

• cites LPS19Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Probably not a substantial claim: may not pass S4 (based). May combine two claims.

A single oracle circuit uses relatively few logical qubits (< 2^20), so layout and communication costs are unlikely to dominate.

“A single oracle circuit uses relatively few logical qubits ( &lt; 2 20 ), so these costs are unlikely to dominate.”

• AssumptionThe authors state this as an assumption: Layout and communication costs for the Grover oracle circuit are ignored.

May combine two claims.

Without a depth restriction, it seems advantageous to use the in-place MixColumn version to minimize both G-cost and DW-cost; for a depth restricted setting, Maximov's circuit seems better due to the square in the depth term in Equation (10).

“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).”

May combine two claims.

For LowMC-128, 192, and 256, the minimum depths are 2^{41.1} c_s, 2^{59.8} c_s, and 2^{76.4} c_s, respectively.

“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 .”

May combine two claims.

Our proposed key expansion minimizes width by not requiring ancilla qubits at all, and reduces depth compared to naive key expansion using ancilla qubits for all key bits.

“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.”

May combine two claims.

In the case k = rn, the probability for a unique K is approximately 1/e ≈ 0.3679, and the probability of exactly one spurious key is the same.

“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.”

• AssumptionThe 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.

Probably not a substantial claim: may not pass S4 (based).

Key expansion is one of the two sources of T gates in the design of AES.

“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.”

May combine two claims.

Maximov's MixColumn circuit has a much lower depth, does not reduce T-depth (which is already 0), and comes at the cost of increased width.

“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.”

• cites Max19Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

May combine two claims.

If rn < k, then K is almost certainly not unique; even rn = k - 3 gives less than a 1% chance of a unique key.

“If rn &lt; k , then K is almost certainly not unique. Even rn = k -3 gives less than a 1% chance of a unique key.”

• AssumptionThe 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.

May combine two claims.

For AES-128, 192, and 256, the minimum depths are 2^{40.2} c_s, 2^{56.2} c_s, and 2^{72.3} c_s, respectively.

“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.”

May combine two claims.

Our approach to key expansion works completely in place and reduces width and depth at the same time, in contrast to [LPS19] which uses ancilla qubits for round keys.

“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.”

• cites LPS19Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites GLRS16Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

May combine two claims.

For AES-128 and AES-192, G_D G_W is smaller for the in-place MixColumn implementation, while G_D^2 G_W is smaller for Maximov's circuit.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

The S-box is the only source of T gates in a quantum circuit of AES.

“The S-box is the only source of T gates in a quantum circuit of AES.”

May combine two claims.

Using r=3 for AES-256 guarantees a unique key with overwhelming probability; the probability of no spurious keys is 1-ε with ε < 2^-128.

“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 ϵ &lt; 2 -128 , ϵ &lt; 2 -64 and ϵ &lt; 2 -128 , respectively.”

May combine two claims.

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.

“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.”

May combine two claims.

The DW-cost is better in our work as we increase width by factors less than 4 and simultaneously reduce depth by more than that.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

For AES-128 under MAXDEPTH = 2^96, the attack does not require any parallelization.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Costing the T depth of the dummy AES operation (with the placeholder S-box) returns the expected value of 2 × # of rounds × d, where d is the depth of the dummy S-box.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing).

The Q# compiler is currently unable to optimize a given circuit by searching through small circuit variations that may result in functionally the same operation at a smaller cost.

“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).”

Probably not a substantial claim: may not pass S3 (load-bearing).

The AND and Toffoli gate designs chosen use measurements, hence CNOT, 1-qubit Clifford, measurement and depth counts are probabilistic.

“The AND and Toffoli gate designs we chose use measurements, hence CNOT, 1-qubit Clifford, measurement and depth counts are probabilistic.”

May combine two claims.

The full LowMC encryption circuit for L5 has #CNOT 5070324, #1qCliff 14274, #T 15960, #M 0, T-depth 76, full depth 693471, and width 1915.

“| LowMC L5 | 5070324 | 14274 | 15960 | 0 | 76 | 693471 | 1915 |”

May combine two claims.

The full LowMC encryption circuit for L3 has #CNOT 2271870, #1qCliff 9398, #T 12600, #M 0, T-depth 60, full depth 319317, and width 1483.

“| LowMC L3 | 2271870 | 9398 | 12600 | 0 | 60 | 319317 | 1483 |”

Probably not a substantial claim: may not pass S3 (load-bearing).

For the Q# simulator to run, they are required to use the Microsoft QDK standard library's Toffoli gate for evaluating both Toffoli and AND gates, resulting in deeper than necessary circuits.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing).

They have to explicitly SWAP values across wires, costing 3 CNOT gates, rather than keeping track of free rewiring.

“We also have to explicitly SWAP values across wires, which costs 3 CNOT gates, rather than simply keeping track of the necessary free rewiring.”

May combine two claims.

The full LowMC encryption circuit for L1 has #CNOT 689944, #1qCliff 4932, #T 8400, #M 0, T-depth 40, full depth 98699, and width 991.

“| LowMC L1 | 689944 | 4932 | 8400 | 0 | 40 | 98699 | 991 |”

May combine two claims.

Using r=2 for AES-128 guarantees a unique key with overwhelming probability; the probability of no spurious keys is 1-ε with ε < 2^-128.

“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 ϵ &lt; 2 -128 , ϵ &lt; 2 -64 and ϵ &lt; 2 -128 , respectively.”

May combine two claims.

Using r=2 for AES-192 guarantees a unique key with overwhelming probability; the probability of no spurious keys is 1-ε with ε < 2^-64.

“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 ϵ &lt; 2 -128 , ϵ &lt; 2 -64 and ϵ &lt; 2 -128 , respectively.”

May combine two claims.

The LowMC S-box can be implemented in-place with depth 5 and T-depth 3, or out-of-place with T-depth 1.

“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.”

May combine two claims.

Even without parallelization, more than 2 plaintext-ciphertext pairs are never required for AES-128 and AES-192, and 4 or more pairs are never required for AES-256.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing).

The in-place LowMC S-box design requires ancilla qubits as part of the concrete CCNOT implementation.

“We note that the in-place design does require ancilla qubits as part of the concrete CCNOT implementation.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The Q# Toffoli simulator does not currently support PRNG seeding for de-randomizing measurements, so estimating circuits may result in slightly different numbers.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing).

For AES-128 under MAXDEPTH = 2^96, its cost is underestimated by the approximation.

“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.”

May combine two claims.

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.

“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.”

• AssumptionThe authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
• AssumptionThe 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.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

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.

“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.”

• cites [GLRS16]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

May combine two claims.

ShiftRow is a permutation on the full 128-bit AES state and can be entirely encoded as rewiring.

“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.”

• cites DR99Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Probably not a substantial claim: may not pass S4 (based).

The total distance any signal must travel in the assumed H-tree network is proportional to sqrt(S).

“The total distance any signal must travel is proportional to the square root of the size of this tree, i.e. √ S .”

May combine two claims.

For two oracle circuits G and F, total G-cost is lower for G if and only if G_D G_G < F_D F_G; i.e., one wishes to minimize the product G_D G_G.

“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 &lt; F D F G . That is, we wish to minimize the product G D G G .”

May combine two claims.

In both outer and inner parallelization, one obtains only a factor sqrt(S) gain in the number of Grover iterations when working with S parallel Grover oracles, and this is asymptotically optimal.

“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.”

• cites [Zal99]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• AssumptionThe authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
• AssumptionThe 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.

May combine two claims.

It holds that p/c_p < 1.45, so (pC/(c_p G_G))^2 < 2.11, and for p=1, (pC/(c_p G_G))^2 = 16/π^2 · C^2/G_G^2 ≈ 1.62 · C^2/G_G^2 ≤ 1.62.

“It holds that p/c p &lt; 1 . 45, so ( pC/ ( c p G G )) 2 &lt; 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.”

May combine two claims.

The lower- and upper-triangular components L and U of the PLU decomposition can be implemented with CNOT gates, while the final permutation P requires no quantum gates and is realized by rewiring.

“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.”

May combine two claims.

Dividing the search space separates spurious keys into different subsets and reduces the search problem to finding a unique key, allowing reduction of the number r of message blocks in the Grover oracle.

“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.”

• cites [KHJ18]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• AssumptionThe authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
• AssumptionThe 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.

May combine two claims.

When optimizing the DW-cost metric with a depth restriction, Maximov's circuit should be preferred; if there is no depth restriction, the in-place design leads to a lower DW-cost.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing).

All quantum circuits for AES and LowMC described in the paper were designed, tested, and costed in the Q# programming language.

“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.”

• cites [SGT + 18]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• AssumptionThe 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.

May combine two claims.

High parallelization makes spurious keys irrelevant, and the Grover oracle can use the smallest r such that SKP(k,n,r,S) is still small enough.

“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.”

• AssumptionThe authors state this as an assumption: Any quantum adversary is bounded by a constraint on its total depth for running a quantum circuit.
• AssumptionThe 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.
• AssumptionThe 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.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

RotByte is a circular left shift of a word by 8 bits and can be implemented by appropriate rewiring.

“Similarly, RotByte is a circular left shift of a word by 8 bits, and can be implemented by appropriate rewiring as well.”

May combine two claims.

Kim et al. 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.

“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.”

• cites [KHJ18]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

May combine two claims.

The Q# compiler found non-trivial parallelization between components of the S-box and the surrounding circuit, as evidenced by a dummy AES design having the expected T-depth.

“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.”

May combine two claims.

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.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing).

For LowMC inside Picnic, the full S-boxLayer consists of 10 parallel S-boxes run on the 30 low order bits of the state.

“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.”

May combine two claims.

Studying the original LowMC design results in a sub-optimal circuit, which can be improved by porting the more recent version from [DKP+19].

“This results in a sub-optimal circuit, which can clearly be improved by porting the more recent version from [DKP + 19] instead.”

• cites DKP+19Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

May combine two claims.

For Picnic, all KM_i matrices are invertible, so PLU decomposition can be used for KeyExpansion.

“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.”

May combine two claims.

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.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Picnic proposes three parameter sets with (key size, block size) ∈ {(128,128), (192,192), (256,256)}.

“In particular, Picnic proposes three parameter sets, with (key size , block size) ∈ { (128 , 128) , (192 , 192) , (256 , 256) } .”

Probably not a substantial claim: may not pass S4 (based).

The NIST cost formula does not take into account that parallelization often allows reducing 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.

“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 .”

May combine two claims.

In Picnic, for every round and every parameter set, all LinearLayer matrices are invertible, so matrix multiplication can be implemented via a PLU decomposition.

“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.”

May combine two claims.

If a success probability lower than 1 is acceptable, r=ceil(k/n) plaintext-ciphertext pairs suffice; specifically r=1 for AES-128, r=2 for AES-192, and r=2 for AES-256.

“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.”

• cites LPS19Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.