Comment by bjourne
2 years ago
HN readers that don't want to read the piece in full can take solace in that PQC has not been proven viable. Thus, what algorithms we should use to protect ourselves once what we thought was intractable becomes tractable may be a moot point. Shor's algorithm is capable of factoring 21 into 7 x 3. That's a long way off from factoring the thousands of digits-long numbers used for modern cryptography.
> Shor's algorithm is capable of factoring 21 into 7 x 3. That's a long way off from factoring the thousands of digits-long numbers
That is quite misleading, per my understanding.
Today's or near-future quantum computers can do this level of arithmetic, but Shor's algorithm does not have hardware limitations because it's an algorithm and not a computer. You can apply it to a thousand digits as well as to one. Apparently the thousand digits requires a certain number of qubits, i.e. a big enough quantum computer, but that's kind of the point: many people expect that we will gain that capability (keeping enough qubits stable for long enough to do the computation) sooner or later. Security agencies are saying to expect it in about ten years from now. Maybe you know better, yes can be, but that is not where I am going to put my money.
There now exist algorithms that can mitigate this risk, might as well use them. Why try to convince people they shouldn't bother?
Right, implementations of Shor's algorithm on existing quantum computers can only factor 7 x 3. But even if quantum computing power doubled every year it would still take decades before breaking modern crypto becomes viable. That would require many scientific and engineering breakthroughs. Possible of course, but I wouldn't bet on it.