[Cryptography] Has quantum cryptanalysis actually achieved anything?

[Jon Callas]

> On Mar 11, 2025, at 18:50, Viktor Dukhovni <cryptography at dukhovni.org> wrote:
> 
> On Tue, Mar 11, 2025 at 04:58:39PM -0400, Jerry Leichter wrote:
> 
>> Block ciphers like AES - and symmetric cryptography in general - are
>> not particularly vulnerable to quantum computer attacks.  (The best
>> attack known on such algorithms use Grover's algorithm, which turns
>> brute force search from O(N) to O(SQRT(N)), where N would be 2^n for
>> an n-bit key.  So it reduces your security level by 1 bit.)
> 
> Actually, it halves the number of bits: sqrt(2^n) = 2^{n/2}.  So, in
> theory, a 256-bit key would be brute-forced in 2^{128} time, and a
> 128-bit key in 2^{64} time.  Whether this ever works in practice remains
> to be seen.

There seems to be a consensus among QIS people I've been reading that Grover's algorithm  is impractical for anything cryptographically relevant for space reasons as well as time. AES-128 is still on cipher lists as before.

I don't understand it well enough to explain it. If someone does, it would be nice to hear. 

In any event, the advice to just use a 256-bit cipher and stop worrying is good advice because then we don't have to debate it.

	Jon