3 ms·

How fucked is https and cryptography if this turns out to be true?

patrickmn 7y ago
not
mtgx 7y ago
This quantum computer is not nearly powerful enough to break cryptography right now. To better understand the difference is kind of how they've just invented computers that use transistors and can do some basic math calculations much faster than previous calculating machines, and someone asks "Okay, so when will we be able to play 3D games on this thing?"
skywhopper 7y ago
This is nowhere close to breaking PKI algorithms. The quantum algorithm that can break PKI (Shor’s algorithm) will require processors of hundreds or possibly thousands of qubits. This 53-qubit processor is the current state of the art, and there are huge engineering and interference challenges to overcome as the qubit count increases. As for where we are with Shor’s algorithm, it works by figuring out the prime factors of an integer (which is how RSA keys are constructed). In 2001, IBM factored the number 15 (into 3 x 5) using a quantum computer with 7 qubits. In 2012, they were able to factor 21 into 3 x 7, which is currently the largest number factored using Shor’s algorithm. Given that cryptographic keys run into the hundreds and thousands of bits, Shor’s algorithm isn’t going to be a threat anytime soon. But note, too, that it’s focused on RSA, which is the original PKI algorithm. Newer algorithms exist which aren’t threatened by Shor’s algorithm, and work is already underway to develop new quantum-resistant PKI algorithms. We’ll hear about it when low-bit RSA is easily cracked. And for several years it will be good enough to just increase bit lengths to stay ahead of it. Given all of that, I’d expect it’ll be 20-30 years before quantum computers are a threat to today’s PKI. And by then, PKI will be 20-30 years on from what it is now.
- fsh 7y ago
  It is also worth noting that breaking RSA with Shor's algorithm requires thousands of _error-corrected_ qubits. This corresponds to millions of physical qubits with typical fidelities and nobody knows how to scale a system to that size.

not

mtgx 7y ago

This quantum computer is not nearly powerful enough to break cryptography right now. To better understand the difference is kind of how they've just invented computers that use transistors and can do some basic math calculations much faster than previous calculating machines, and someone asks "Okay, so when will we be able to play 3D games on this thing?"

skywhopper 7y ago

This is nowhere close to breaking PKI algorithms. The quantum algorithm that can break PKI (Shor’s algorithm) will require processors of hundreds or possibly thousands of qubits. This 53-qubit processor is the current state of the art, and there are huge engineering and interference challenges to overcome as the qubit count increases. As for where we are with Shor’s algorithm, it works by figuring out the prime factors of an integer (which is how RSA keys are constructed). In 2001, IBM factored the number 15 (into 3 x 5) using a quantum computer with 7 qubits. In 2012, they were able to factor 21 into 3 x 7, which is currently the largest number factored using Shor’s algorithm. Given that cryptographic keys run into the hundreds and thousands of bits, Shor’s algorithm isn’t going to be a threat anytime soon. But note, too, that it’s focused on RSA, which is the original PKI algorithm. Newer algorithms exist which aren’t threatened by Shor’s algorithm, and work is already underway to develop new quantum-resistant PKI algorithms. We’ll hear about it when low-bit RSA is easily cracked. And for several years it will be good enough to just increase bit lengths to stay ahead of it. Given all of that, I’d expect it’ll be 20-30 years before quantum computers are a threat to today’s PKI. And by then, PKI will be 20-30 years on from what it is now.

fsh 7y ago
It is also worth noting that breaking RSA with Shor's algorithm requires thousands of _error-corrected_ qubits. This corresponds to millions of physical qubits with typical fidelities and nobody knows how to scale a system to that size.