4 ms·

> The largest number reliably factored by Shor's algorithm is 21 which was factored in 2012.[0] So for the time being quantum is not a real thread to cryptogra

> The largest number reliably factored by Shor's algorithm is 21 which was factored in 2012.[0] So for the time being quantum is not a real thread to cryptography and there sound technical reasons to assume that it never will be. [0] https://en.wikipedia.org/wiki/Integer_factorization_records#Records_for_efforts_by_quantum_computers https://en.wikipedia.org/wiki/Integer_factorization_records#...

clavigne 5y ago
Correct. There is a lot of arguments around that quantum computing will scale in a Moore's Law way (wrt qubits, so doubly exponential in compute power) and thus will be useful in the near future. These are extremely optimistic. Quantum computing hardware just came out of academic lab in the last few years and was subjected to actual engineering, hence the massive growth in capabilities. However these were mostly the result of solving all kind of low hanging fruits. To give an example of what I mean, I talked to a physicist doing superconducting qubit work at a conference in 2015 and at the time the cavities used to hold qubit wavefunction where machined by the Dept machine shop, using a mill. He told me they would just keep making them until they had enough that were of sufficient quality for computation. If I remember properly something like 1 was kept and 20 thrown. Using proper manufacturing can get you a lot farther but... It's unclear how far, and modern (non quantum resistant) encryption would require thousands of time more qubits to solve on QC than are currently there. https://www.technologyreview.com/2019/05/30/65724/how-a-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours/ https://www.technologyreview.com/2019/05/30/65724/how-a-quan...
nieve 5y ago
Generally when you're talking about cryptography you don't want to make assumptions that rely on reality working out in the way that's most convenient for you. Presuming that quantum computing can't be any kind of threat is a pretty risky gamble.
- astrange 5y ago
  The NSA actually seems quite scared of it and wants everyone to move to post-quantum encryption already. Ulterior motives here would imply they have cracks for everything except quantum encryption, which probably isn't the case. https://arstechnica.com/information-technology/2015/08/nsa-preps-quantum-resistant-algorithms-to-head-off-crypto-apocolypse/ https://arstechnica.com/information-technology/2015/08/nsa-p...
upofadown 5y ago
There is some opinion that the 21 factorization, and the 15 factorization for that matter, depended on knowledge of the correct result[1]. [1] https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm https://crypto.stackexchange.com/questions/59795/largest-int...

clavigne 5y ago

Correct. There is a lot of arguments around that quantum computing will scale in a Moore's Law way (wrt qubits, so doubly exponential in compute power) and thus will be useful in the near future. These are extremely optimistic. Quantum computing hardware just came out of academic lab in the last few years and was subjected to actual engineering, hence the massive growth in capabilities. However these were mostly the result of solving all kind of low hanging fruits. To give an example of what I mean, I talked to a physicist doing superconducting qubit work at a conference in 2015 and at the time the cavities used to hold qubit wavefunction where machined by the Dept machine shop, using a mill. He told me they would just keep making them until they had enough that were of sufficient quality for computation. If I remember properly something like 1 was kept and 20 thrown. Using proper manufacturing can get you a lot farther but... It's unclear how far, and modern (non quantum resistant) encryption would require thousands of time more qubits to solve on QC than are currently there. https://www.technologyreview.com/2019/05/30/65724/how-a-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours/ https://www.technologyreview.com/2019/05/30/65724/how-a-quan...

nieve 5y ago

Generally when you're talking about cryptography you don't want to make assumptions that rely on reality working out in the way that's most convenient for you. Presuming that quantum computing can't be any kind of threat is a pretty risky gamble.

astrange 5y ago
The NSA actually seems quite scared of it and wants everyone to move to post-quantum encryption already. Ulterior motives here would imply they have cracks for everything except quantum encryption, which probably isn't the case. https://arstechnica.com/information-technology/2015/08/nsa-preps-quantum-resistant-algorithms-to-head-off-crypto-apocolypse/ https://arstechnica.com/information-technology/2015/08/nsa-p...

upofadown 5y ago

There is some opinion that the 21 factorization, and the 15 factorization for that matter, depended on knowledge of the correct result[1]. [1] https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm https://crypto.stackexchange.com/questions/59795/largest-int...