5 ms·

Quantum computers can, in general, provide up to a quadratic speedup over classical algorithms and WILL in fact be enough. Once we have QCs all bets are off.

VLM 14y ago
No, not really. Run the same example from the article with a quadratic speedup and see how scalable it is. 56 bit DES should be nervous. 256 bit AES, not so much. There is a tiresome often repeated quantum computing meme or anti-pattern where QC is a magic implementation such that "my magic can do anything I can dream of". Well no, not really. Oh it could be powerful, maybe even implementable, but not limitless.
- apawloski 14y ago
  To clarify a bit further, only a few cryptosystems (certain public key systems) are really threatened by quantum computers. Theoretically, literature indicates that quantum computers are really good at factoring large numbers [1], and they are really good at solving discrete log problems [2]. So yes, QCs are theoretically able to crack in linear time some systems whose security depends on those problems being hard (eg ElGamal, RSA). But systems that don't rely on large primes/discrete logs (eg symmetric algorithms like AES) are not vulnerable to quantum computers. (At least not vulnerable in the "throw them out, they're useless now" sense.) In fact, there's even asymmetric cryptosystems that aren't threatened by quantum computers [3]. Again, any system that doesn't rely on large primes, or the difficulty of the discrete log problem, is not significantly threatened. [1]http://arxiv.org/abs/quant-ph/9503007 http://arxiv.org/abs/quant-ph/9503007 [2]http://epubs.siam.org/doi/abs/10.1137/S0097539795293172?journalCode=smjcat http://epubs.siam.org/doi/abs/10.1137/S0097539795293172?jour... [3]http://link.springer.com/chapter/10.1007%2F3-540-44586-2_2?LI=true http://link.springer.com/chapter/10.1007%2F3-540-44586-2_2?L...
cbr 14y ago
DJB claims QCs don't break AES: http://cr.yp.to/talks/2008.10.18/slides.pdf http://cr.yp.to/talks/2008.10.18/slides.pdf
betterunix 14y ago
If QC is even possible (it seems an awful lot like cold fusion at this point -- always on the horizon, yet some issue prevents it from being realized), it wouldn't kill crypto. A hypothetical "triple-AES" would mitigate a quadratic attack. Lattice/linear code cryptosystems can provide security against quantum computing for public key systems. All a QC would do to cryptography is force everyone to use different algorithms, which is about as useful as forcing everyone to wear different colored clothing.

VLM 14y ago

No, not really. Run the same example from the article with a quadratic speedup and see how scalable it is. 56 bit DES should be nervous. 256 bit AES, not so much. There is a tiresome often repeated quantum computing meme or anti-pattern where QC is a magic implementation such that "my magic can do anything I can dream of". Well no, not really. Oh it could be powerful, maybe even implementable, but not limitless.

apawloski 14y ago
To clarify a bit further, only a few cryptosystems (certain public key systems) are really threatened by quantum computers. Theoretically, literature indicates that quantum computers are really good at factoring large numbers [1], and they are really good at solving discrete log problems [2]. So yes, QCs are theoretically able to crack in linear time some systems whose security depends on those problems being hard (eg ElGamal, RSA). But systems that don't rely on large primes/discrete logs (eg symmetric algorithms like AES) are not vulnerable to quantum computers. (At least not vulnerable in the "throw them out, they're useless now" sense.) In fact, there's even asymmetric cryptosystems that aren't threatened by quantum computers [3]. Again, any system that doesn't rely on large primes, or the difficulty of the discrete log problem, is not significantly threatened. [1]http://arxiv.org/abs/quant-ph/9503007 http://arxiv.org/abs/quant-ph/9503007 [2]http://epubs.siam.org/doi/abs/10.1137/S0097539795293172?journalCode=smjcat http://epubs.siam.org/doi/abs/10.1137/S0097539795293172?jour... [3]http://link.springer.com/chapter/10.1007%2F3-540-44586-2_2?LI=true http://link.springer.com/chapter/10.1007%2F3-540-44586-2_2?L...

cbr 14y ago

DJB claims QCs don't break AES: http://cr.yp.to/talks/2008.10.18/slides.pdf http://cr.yp.to/talks/2008.10.18/slides.pdf

betterunix 14y ago

If QC is even possible (it seems an awful lot like cold fusion at this point -- always on the horizon, yet some issue prevents it from being realized), it wouldn't kill crypto. A hypothetical "triple-AES" would mitigate a quadratic attack. Lattice/linear code cryptosystems can provide security against quantum computing for public key systems. All a QC would do to cryptography is force everyone to use different algorithms, which is about as useful as forcing everyone to wear different colored clothing.