Grover Attack Aes Key Size Analysis

Short answer: Published papers give circuit designs and resource estimates for running Grover's algorithm against AES-128, AES-192 and AES-256, counting qubits, gates and depth. These are paper estimates for a fault-tolerant machine that does not exist today, and the later 2019 work lowered the cost estimates for the post-quantum security categories. Nothing here describes an attack that has been carried out.

What resources are required for the attack?

The analysis focuses on the cost of implementing the quantum algorithm using specific metrics. The authors of a 2015 paper (arXiv 1512.04965) measure this cost by evaluating the overall circuit size, the number of qubits, and the circuit depth. The underlying logical quantum gate set used for these estimates is the Clifford + T gate set. This choice is motivated by the fact that this gate set can be implemented fault-tolerantly on a large set of codes, including the surface code family and concatenated CSS codes.

For the specific case of AES, the authors establish precise bounds for the number of qubits and the number of elementary logical quantum gates. They provide reversible circuits that implement the full AES function for each standardized key size. The resource estimates include counts for Toffoli gates, controlled NOT gates, and NOT gates. The implementation requires that the Boolean predicate queried in Grover’s algorithm be realized as a reversible circuit. This means the operation must be possible via an embedding into a permutation.

How does the depth restriction affect the design?

Previous work on AES focused on minimizing the number of qubits while deriving the full gate cost. In contrast, a 2019 paper (ePrint 2019/1146) examines the cost of quantum key search attacks under a depth restriction. Its techniques aim to reduce the oracle depth, even if it requires using more qubits. The goal is to achieve a lower overall attack cost in both the gate count and the depth-times-width cost models.

The depth of the circuit is a critical measure for the cost of the presented quantum algorithms. By optimizing for depth, researchers can design circuits that are more efficient in terms of execution time, although this may trade off against the total number of qubits required. This approach provides new, lower cost estimates for the quantum key search against AES. These estimates are relevant for assessing the security of post-quantum cryptography, where security categories are defined based on the concrete cost of such attacks.

Which key sizes are covered by the analysis?

The analysis covers all three variants of AES that are standardized in FIPS-PUB 197. These variants correspond to key sizes of 128, 192, and 256 bits. The researchers establish precise bounds for the number of qubits and the number of elementary logical quantum gates needed to implement Grover’s algorithm for each of these sizes. The objective is to extract the key from a small number of AES plaintext-ciphertext pairs.

The Boolean predicate that is queried in Grover’s algorithm must be realized as a circuit for each key size. The seemingly simple task of implementing the AES function requires analysis because the circuit implementation is required to be reversible. The resource estimates provided for these key sizes allow for a comparison of the quantum resources required for different levels of security. The study highlights that even for the most obvious target, detailed logical level resource estimates were previously unavailable.

What are the implications for post-quantum security?

In the post-quantum cryptography standardization process, security categories are defined based on the concrete cost of quantum key search against AES. The work presents new, lower cost estimates for each category, which has immediate implications for the security assessment of post-quantum cryptography. By providing more accurate and lower cost estimates, the research refines the understanding of the threat posed by Grover’s algorithm.

The 2019 authors release Q# implementations of the full Grover oracle for AES-128, -192, and -256. These implementations include unit tests and code to reproduce the quantum resource estimates. They state that, to their knowledge, these are the first such full implementations and automatic resource estimations. A revised version of the work corrects the estimates for AES to account for issues in Q# that made the original estimates inaccurate. This correction ensures that the resource counts are more reliable for security analysis.

FAQ

Does Grover’s algorithm provide a speed-up for AES?

In the papers' framing, Grover's search gives a square root speed-up over classical exhaustive key search. The papers estimate what that costs in logical qubits and gates.

Is the AES circuit implementation reversible?

Yes, the circuit implementation is required to be reversible. This means it must be possible to implement the operation via an embedding into a permutation, which is a necessary condition for the quantum algorithm.

Which gate set is used for the resource estimates?

The estimates use the Clifford + T gate set as the underlying fault-tolerant logical quantum gate set. This set is chosen because it can be implemented fault-tolerantly on various quantum error-correcting codes.

Are there implementations available for these circuits?

The 2019 paper says it releases Q# implementations of the full Grover oracle for AES-128, -192, and -256 are released. These include unit tests and code to reproduce the quantum resource estimates, representing the first such full implementations.

Does the depth optimization reduce the total cost?

According to the 2019 paper, techniques that reduce the oracle depth can lower the overall attack cost in both gate count and depth-times-width models, even if they require more qubits.