1
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ "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 $\endgroup$
    – poncho
    Apr 17, 2023 at 15:13

1 Answer 1

1
$\begingroup$

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.

This is not the only way in which Kyber might be attackable with quantum resources. It is known that there is a connection between short vector problems and hidden dihedral subgroups, much as there is a connection between factoring/discrete logarithms and hidden abelian subgroups. However, analysis of how the quantum dihedral Fourier transform could be used to attack these problems has not yet had the success of shorts algorithm with the quantum abelian Fourier transform.

$\endgroup$
2
  • $\begingroup$ You have to solve AES256 key recovery, how about triple 256-bit AES? Ambit inc said Kyber1024 has 230 bit quantum security, which may require triple AES (like 3DES before AES was published). $\endgroup$
    – Flan1335
    May 7, 2023 at 9:58
  • $\begingroup$ I don't consider the Ambit white paper to be well-informed. $\endgroup$
    – Daniel S
    May 7, 2023 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.