[Cryptography] Has quantum cryptanalysis actually achieved anything?

[Richard Carback]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256



> On Mar 12, 2025, at 2:27 PM, Jon Callas <jon at callas.org> wrote:
> 
>> 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.

I’ve not seen a believable grover simulator implementation, but in the Shor’s case these things get defined in terms of number of Toffoli Gate operations. From there you can calculate how many physical qubits are needed for gates and memory based on expected error rates, how many runs it will require, how much time each run will take, and ultimately how much power is needed (best estimate is ~20k USD for ECC). My understanding for all of these is that grover requires a lot more gates/resources but I’ll admit it is a known unknown at this point.

The quantum doom clock links the actual research papers for ECC and RSA anyone wants to dig into it.

> 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.

This is the right advice. I think you’d be safe even post quantum breakthrough even at 128 for at least another 10 years or so, but that’s my opinion and facts may vary.

-Rick
-----BEGIN PGP SIGNATURE-----
Version: ProtonMail

wsGpBAEBCABdBYJn1EezCZA/GuWbfQE6TTUUAAAAAAAcABBzYWx0QG5vdGF0
aW9ucy5vcGVucGdwanMub3JnKy4RcWd6pfyLoABaRhdm9RYhBAGFytdGt1Ef
10NhlD8a5Zt9ATpNAADFmA/8D5Sn5N4rW7YImFiPyuH+nx98Iqn4i045oqVI
S8tLSVa9rNldVXGxw/oFWIPDKunqSW3o+e3j368vxvqx0v5BWLOXSXYHkfIv
aHsGnng9AjUpGWYmIPFxsH8mnx6tutoYHTk7r14FWbgJDnwHID15/z/fRmSl
ldPOEM/ns6vSKwnQHlBCfxnh/3QokTcp6wepzJY+OGqr1OmZVnN5m8HwA8io
zssW0SokiCEOt9lozkeu4C0bImxgqxja9xT7GrJVl/PcztPpz5t7O0DztQWx
xRIuyeQcj4ZIeaE1ngirNxr6x924qTrEkk1jOonhIJAHbv65PTQVg51qxvje
nT9B93qAOgr3Rbn3Ta6ymoT6gmzoc047JS9RKLnHQLfa/hM+PJSobLP9ft/b
zij77M9DXTra1MEfH2XyUZYAdI4qI+fqup46rSKg/grKskDWEiuXgRbOQJ3f
mfLdXY4GtbOA9HO7BNtPb9pOSTwbBioUZE0egsSCN0i9OBwxJhUAnWAU6JaP
l89HDKWolni/WSZ3j8MCniAJgrTbTLQ/fOOHzt5oaqKTPZ7Y6usN2Kti6u8X
vzqOPHSjBEdsNhai0cbmccrSIAWxER7eUgbD7YOlwdm+EVWbd58nIMyLbsn9
sGNWK2sAR9aaju/KRQfaTTGXxf51U2dQIIEhoScrnVeW1e8=
=KlQc
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: publickey - rick at carback.us - 0x0185CAD7.asc
Type: application/pgp-keys
Size: 3147 bytes
Desc: not available
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20250314/4c7000b6/attachment.key>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: publickey - rick at carback.us - 0x0185CAD7.asc.sig
Type: application/pgp-signature
Size: 636 bytes
Desc: not available
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20250314/4c7000b6/attachment.sig>