5 ms·

Yeah, this article seems pretty wrong to me. However! I believe that Grover's algorithm will not be a very big deal, at least in early-ish quantum computers.

Yeah, this article seems pretty wrong to me. However! I believe that Grover's algorithm will not be a very big deal, at least in early-ish quantum computers. * The speedup is proportional to the depth of the quantum computation, measured in oracle calls. So we're talking maybe 2^40 speedup, not 2^64 or 2^128. * There is a significant cost in converting practical algorithms to run on a QC, because QC algorithms have to be reversible. * Early QCs will have a huge overhead from quantum error correction. * Just guessing, but early QCs will probably have lower clock speed (taking long to compute a gate than a classical computer uses for a whole clock period), a higher fabrication cost and a vastly higher error energy usage due to the fridge and classical electronics. Divide that 2^40 by all these factors and you can see that it won't get very far, at least until all these "early QC" problems can be solved. So the impact on symmetric crypto probably won't be much at all, but moving from 128-bit keys to 192-bit keys would be plenty. The above mostly does not apply to Shor's algorithm. Shor might be slow on early QCs, but it's exponentially faster than any known classical algorithm, instead of only linearly faster.

Vecr 4y ago
AES-192 is a bit weird, I'd use AES-256 instead because it gives you more buffer against the problems caused by the block size and key size not matching. Or just use ChaCha20 in an AEAD configuration.
- less_less 4y ago
  Sure, AES-256 or ChaCha20 is probably an even better choice. I just mean to say that even a 192-bit key is comfortably out of reach of Grover-assisted brute-force for the foreseeable future, which would not be true if Grover effectively halved the key size. I'm not aware of problems with the AES block size and key size not matching... is there some cryptanalysis in that direction? On the contrary, I'd thought that AES-256 had a slightly shakier key schedule than AES-128 or -192, though due to the longer key it is still stronger than AES-192 vs known attacks.
  - Vecr 4y ago
    I'm actually not sure, I would need to look at it again. As you said, AES-128 is probably the most sound in a theoretical sense, but AES-256 stronger against brute force and that makes up for the theoretical problems. AES-192 is a weird middle option that's less strong against brute force than AES-256, and is also theoretically less sound that AES-128.

Vecr 4y ago

AES-192 is a bit weird, I'd use AES-256 instead because it gives you more buffer against the problems caused by the block size and key size not matching. Or just use ChaCha20 in an AEAD configuration.

less_less 4y ago
Sure, AES-256 or ChaCha20 is probably an even better choice. I just mean to say that even a 192-bit key is comfortably out of reach of Grover-assisted brute-force for the foreseeable future, which would not be true if Grover effectively halved the key size. I'm not aware of problems with the AES block size and key size not matching... is there some cryptanalysis in that direction? On the contrary, I'd thought that AES-256 had a slightly shakier key schedule than AES-128 or -192, though due to the longer key it is still stronger than AES-192 vs known attacks.
- Vecr 4y ago
  I'm actually not sure, I would need to look at it again. As you said, AES-128 is probably the most sound in a theoretical sense, but AES-256 stronger against brute force and that makes up for the theoretical problems. AES-192 is a weird middle option that's less strong against brute force than AES-256, and is also theoretically less sound that AES-128.