[Cryptography] Has quantum cryptanalysis actually achieved anything?

[Bill Stewart]

On 3/11/2025 6:50 PM, Viktor Dukhovni 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.
Also, that's 2^{n/2} steps, but quantum computer steps may end up being 
a lot slower than conventional CPU steps, so there's a few tens of bits 
of extra padding left even in that 128-bit key.