Commenting on this, now that it's making its third or whatever pass on HN. Also Scott Aaronson's comments are interesting: <a href="https://scottaaronson.blog/?p=6670" rel="nofollow">https://scottaaronson.blog/?p=6670</a><p>> The most prominent application by far is the Shor algorithm (opens a new window)for factorising large numbers into their constituent primes, which is exponentially faster than any known corresponding scheme running on a classical computer. Since most cryptography currently used to protect our internet traffic are based on the assumed hardness of the prime factorisation problem, the sudden appearance of an actually functional quantum computer capable of running Shor’s algorithm would indeed pose a major security risk.<p>> Shor’s algorithm has been a godsend to the quantum industry, leading to untold amounts of funding from government security agencies all over the world. However, the commonly forgotten caveat here is that there are many alternative cryptographic schemes that are not vulnerable to quantum computers. It would be far from impossible to simply replace these vulnerable schemes with so-called “quantum-secure” ones.<p>Note that Shor's algorithm breaks not just factoring, but also discrete log, including elliptic curve discrete log. That includes classic DH and DSA of course, as well as ECDSA and ECDH, whether they're over Bitcoin's curve, the other NIST curves, Brainpool, {curve,ed}{25519,448}, pairing-friendly curves, everything. Almost all broadly deployed public-key crypto uses RSA or elliptic curves. Those alternative public-key algorithms are still being worked out, and will take years to broadly deploy, so if a QC gets built, it will probably be able to break into straggling systems for some years. There is also a risk that the replacements will eventually fall to quantum or even classical attack, especially considering that a significant fraction of the proposed replacements already <i>have</i> fallen (most recently SIKE) or been weakened (eg, every multivariate quadratic sig). They may also have other security problems, eg implementation bugs or side-channel attacks.<p>The surviving quantum-secure algorithms are all either pretty inefficient (McEliece and SPHINCS+, and CSIDH and SQISign but those are also bleeding-edge), or use structured lattices (Kyber, Falcon, Dilithium, NTRU and NTRU prime, etc) or structured codes that look kind of like structured lattices (BIKE, HQC). So we'll have most of our eggs in just a couple of baskets again, and outside of applications that can use McEliece and SPHINCS+, they'll be newer, less-tested baskets. Also, while fast, the structured lattice and structured code systems still use significantly more bandwidth that elliptic curves.<p>Using long-term symmetric keys instead of or in addition to public-key crypto is possible in some applications, but it's obnoxious and limiting: you'd end up with some combination of Kerberos derivatives (with trusted third parties acting as single points of security failure), mailed smartcards or other secrets, and physical in-person meetings to set up shared keys.<p>So the bigger issue in my view is that outside of Bitcoin, breaking crypto is mostly a net negative for society. Transitioning to quantum-secure crypto is also a negative, in that it will take a ton of work and the replacements are less efficient than elliptic curves, and may have security problems. (It's also probably unavoidable because governments will try to build QCs to break crypto even if private industry doesn't.) So all this money is being spent on something whose first major application will be negative, if it even works at all. Hopefully the positive stuff will outweigh this.