[Cryptography] Has quantum cryptanalysis actually achieved anything?

[Richard Carback]

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



> On Feb 24, 2025, at 8:36 PM, Jon Callas <jon at callas.org> wrote:
> 
> Real quantum cryptanalysis is, as I understand it (correct me if I'm confused), a teraquop-ish problem (depending on many things for implementing Shor). Assuming there's some sort of exponential growth, akin to Moore's Law, it's not a million times harder to get a teraquop, but we're not going to get a teraquop machine without building a megaquop machine.

The current “best” algorithms ( Chevignard, Fouque, and Schrottenloher for RSA, and Hyeonhak and Hong for ECC) estimate the following logical qubit requirements: 
RSA2048: 2,314
RSA4096: 3,971
ECC256: 1,673
When translated to physical qubits, you need to take into account error correction to build the gates which as of last month I had estimated about 2 million for ECC, but now estimate 650k. The quantum doom clock calculator will let you play around here to see how the numbers change by manipulating the p value. If the physical properties of the gates remain largely the same (cycle times, power requirements, etc), then the time to break may be 8-12 hrs and cost about 20,000 dollars per key in terms of energy. 

> So let me give a prediction for 2030ish. Three things will be in place:
> 
> (1) We have a megaquop machine that's doing some physical simulations that are useful to industry that needs those.
> (2) The PQC migration is mostly done. Most TLS is actively PQC, some other systems like OpenPGP, S/MIME, and full disk encryption are delivered, but we're still not quite there in embedded systems like ATMS and point-of-sale. We understand how we're going to get practical PQC equivalents of unlinkable BBS signatures, zk-proofs, threshold, group and so on. Some is delivered, more is understood, and there are annoying gaps in some of it.
> (3) The mainstream discussions of quantum information science are no longer talking about breaking cryptography except as an aside because of the above. We did it. We obviated the need.

In many ways we are already there, especially for communications and I am pleasantly surprised by this result. I open sourced a proof of concept ratchet on my messaging tool using hybrid classical + pqc in early 2022 and was shocked to see Signal and others go on to do the same thing with much more rigorous review only a year later. My belief was that everyone would drag their feet on this for a decade or more! There’s also TLS upgrades on their way which completely obviate that side of the problem. All of that will definitely be in place by 2030 or sooner. This part of the problem is way more important to me due to the store now decrypt later issue.

DeFI and cryptocurrency protocols in general are lagging behind because they don’t want to be writing image-sized keys to the chain. A billion dollars in a wallet is also a regular thing now, and I think they’re going to be the biggest target if things keep progressing the way they have in the last couple years. They don’t move quickly either, but their growth indicates they may be large enough to cause a real problem with the global economy.

-Rick




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

wsGpBAEBCABdBYJnvgkUCZA/GuWbfQE6TTUUAAAAAAAcABBzYWx0QG5vdGF0
aW9ucy5vcGVucGdwanMub3JnAv2UoJuhmcKrwe/oOmEHbRYhBAGFytdGt1Ef
10NhlD8a5Zt9ATpNAAARJxAAl3/k1zLvJmFgucd2/sAbvsnsbhi84QmM2Hn2
xkkqgyn9K5VtPspIfY+wIlUIkXmTK7pqmYf1j+JrmB7I2QLYiQPofGge4eXt
n6bvdSccynzR9gdQUKej/mHpk0HsfMSBwqxF4AAJmPolFsM4gTevYTc7zD4P
aw+v6EFZyG7LM4YdkMguxJTElRiuTKxkr+6iPgyM/zCD7gu+0Hx/jLRDGXj8
q4zdrH/PjUhbbPWYnkQPX3hdWfyReZkgQ35QKgeihb+V1CL45Bl1RiQaKT3O
1EIBjQ/Px9jON0ATeV+rG/MwZrpBrBtTo9RUFwqdmCVuEG62lbgtxKQ0mtSo
fHq20ouMANrx+FESOV7BsnwHJBEQz5gEkljbvhYFD2Z79sQiY6JlidngGQjt
+c4ZmDwG19NOrmDZ4yUh08OUST6SoEupYWpcrK2XZhkA2vaf4h1QnmYtfGao
p/2gm38BjlLBFWocFiMDmmDCTaB9NVQS9yUYqNZrr0V4cRmbacF/Y4FfNJk8
CVXDOfq0EOQGCg7TgipnHEUbqvjV2ahlEohHu3YT8yckX7VKISA8JU+Kb3Nl
/qyBpG7MF1yBiF54uWRFyzCmetsCKpk8qIAnN3qKzBzU3AqDPo1LE2rK/+Y0
YV4Rh3uLL8Ih2Fs4cXTrfh2ntnOrRPKSEKef0bZLxFhdua8=
=FmAF
-----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/20250225/9d9b7948/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/20250225/9d9b7948/attachment.sig>