When China, the US or Google do break encryption they aren’t going to announce it.
I thought it was already fairly well established that symmetric encryption is not something that a quantum computer could potentially crack, only asymmetric encryption is theoretically possible due to its use of a prime order field.
Shor’s algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor.[1][2] It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms
a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor’s algorithm could be used to break public-key cryptography schemes, such as
- The RSA scheme
- The Finite Field Diffie-Hellman key exchange
- The Elliptic Curve Diffie-Hellman key exchange
Moreover:
The largest number reliably factored by Shor’s algorithm is 21 which was factored in 2012 (ie faster than a regular computer, the much higher records like 48 bit utilized pre and post processing and was faster on a regular computer).
Even if we go with the assumption that the military is 10 years ahead in technology and can factor 221 with Shor’s, that’s still nowhere near enough to break RSA. Much more efficient to attack all the systemic flaws in RSA, hence why 1024 is no longer considered secure, 2048 is assumed to be breakable by any 3 letter agency, 4096 is assumed to be safe (for now), but mostly the latest and greatest is elliptical ECDSA/Ed25519 (of which NIST has been accused of rigging ECDSA for easier cracking lol).
Yep. Technically you could in principle use Grover’s algorithm to speed up cracking a symmetrical cipher, but the size typically used for the keys is too large so even though it’d technically be faster it still not be possible in practice. Even with asymmetrical ciphers we already have replacements that are quantum safe, although most companies have not implemented them yet.
So far the biggest achievement in quantum computing seems to either be making a super random number reasonably quickly, or figuring out what quantum computers might be good for some day. So breaking encryption seems like a big leap.
The original article smelled wrong when they claimed to have broken AES. Thankfully, Bruce Schneier is far more authoritative than I ever will be and gives a short and succinct list of links to debunkings of this.
