Score:1

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

tc flag

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?

poncho avatar
my flag
"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
Score:1
ru flag

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.

Flan1335 avatar
tc flag
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).
Daniel S avatar
ru flag
I don't consider the Ambit white paper to be well-informed.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.