# How long time per operation to crack Kyber1024 compared to AES256 for quantum computers?

How long time does quantum computers take per operation when search the key of Kyber? Grover's algorithm weakens 256-bit AES to 128-bit security, quantum computers at most take 2^128 operations to find AES key, but it must take some time per operation; as mentioned https://www.ambit.inc/pdf/KyberDrive.pdf : Kyber-1024 is known to have 254 bits of classical security and 230 bits of quantum security (coreSVP hardness). Quantum computers at most take 2^230 operations. So which takes longer time per operation, (CAUTION: Not total time, but time per operation)? Kyber1024 or AES256?

• "quantum computers at most take 2^128 operations to find AES key"; technically yes (where an operation is an AES evaluation), however if we are extremely impatient, say, we want the result before the sun turns into a red giant, well, we need to parallelize, and that (unlike parallelization in the classical realm) adds significantly to the number of operations required Apr 17, 2023 at 15:13

If I had resources commensurable with those able to successfully attack AES256 (which is a ridiculous level of economic resource by current understanding), I could attack Kyber by recovering the 256-bit seed value $$d$$ in Algorithm 4 of the Kyber specification. Note that the 256-bit derived value $$\rho$$ is known to me a smart of the public key and so by truncating the output of $$G$$ to 256-bits I have a 256-bit-to-256-bit function where I know an output $$\rho$$ and wish to find the corresponding input $$d$$. Whatever means I have to solve AES256 key recovery (e.g. 256-bit classical exhaustion or 128-bit Grover), I can presumably use to solve this similar problem. The only distinction is in the function evaluation which is either AES or SHA3. Recent work by Song estimates the Toffoli depth of a SHA3 quantum circuit to be 552 or total depth 2020; by comparison Grassl estimates a Toffoli depth for AES of 7488 or total depth 16408, so that AES256 key recovery is perhaps harder 8x harder than Kyber key recovery.