Reply to post: Re: Crypto

IBM cuts ribbon on quantum computing centre wherein a 53-qubit monster lurks

Michael Wojcik Silver badge

Re: Crypto

All the current algorithms are indeed (technical phrase coming here) completely buggered by a sufficiently large quantum computer.

Not true. All the asymmetric-cryptography algorithms (both for signing and for key agreement) in widespread use rely on problems in BQP - specifically, they can be solved in polynomial time using Shor's algorithm with a sufficiently large general quantum computer. But quantum-resistant asymmetric-crypto algorithms date back to the 1970s (McEliece, Merkle, etc).

In their original forms, the quantum-resistant algorithm families all offered too high performance penalties and/or key sizes versus RSA, discrete DH, and ECC DH. But this has been a very active area of research, and of course computing resources are somewhat more generous now than they were forty years ago. Google did a trial of some "post-quantum crypto" in real-world use a while back; the algorithms are good enough now to be used by sites that don't need the absolute best performance.

For symmetric cryptography, Grover's algorithm offers an exponential speedup in brute-forcing, but the exponent is only 1/2 so doubling the key length negates the advantage, even if operations in your QC were as fast as they were on your conventional computer. Which they wouldn't be.

And, frankly, it's not just a matter of "scaling up"; there are good reasons to doubt that large general QCs are even feasible. If they are, they'd be so wildly expensive and resource-hungry that even state actors wouldn't be able to use them for routine key-breaking.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

SUBSCRIBE TO OUR WEEKLY TECH NEWSLETTER

Biting the hand that feeds IT © 1998–2019