Applying Grover's algorithm to AES: quantum resource estimates
arXiv:1512.04965
Abstract
We present quantum circuits to implement an exhaustive key search for the Advanced Encryption Standard (AES) and analyze the quantum resources required to carry out such an attack. We consider the overall circuit size, the number of qubits, and the circuit depth as measures for the cost of the presented quantum algorithms. Throughout, we focus on Clifford gates as the underlying fault-tolerant logical quantum gate set. In particular, for all three variants of AES (key size 128, 192, and 256 bit) that are standardized in FIPS-PUB 197, we establish precise bounds for the number of qubits and the number of elementary logical quantum gates that are needed to implement Grover's quantum algorithm to extract the key from a small number of AES plaintext-ciphertext pairs.
arXiv comment13 pages, 3 figures, 5 tables; to appear in: Proceedings of the 7th International Conference on Post-Quantum Cryptography (PQCrypto 2016)
References in corpus (10)
- Elementary gates for quantum computation
- Surface codes: Towards practical large-scale quantum computation
- Quantum Amplitude Amplification and Estimation
- A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
- High threshold universal quantum computation on the surface code
- Overhead and noise threshold of fault-tolerant quantum error correction
- Fixed-point quantum search with an optimal number of queries
- Novel constructions for the fault-tolerant Toffoli gate
- On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
- On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography