  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 $O(\sqrt{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.
