[Cryptography] Has quantum cryptanalysis actually achieved anything?

[Viktor Dukhovni]

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.

    https://gilkalai.wordpress.com/2025/02/17/robert-alicki-michel-dyakonov-leonid-levin-oded-goldreich-and-others-a-summary-of-some-skeptical-views-on-quantum-computing/
    https://gilkalai.wordpress.com/2025/02/26/quantum-computing-skepticism-part-2-my-view-and-responses-to-skeptical-claims-featuring-john-preskill-scott-aaronson-dave-bacon-aram-harrow-and-boaz-barak/

-- 
    Viktor.