The reason 256 bit AES keys are large enough is that in order to brute-force them, one of 2 things needs to happen:
(1) We need to build computers out of something other than matter
or
(2) A weakness in AES must be discovered that will need to reduce the search space significantly
We can disregard (1) as it will probably require changing (almost) all encryption algorithms that we currently use. (2) will most likely break all key-lengths so any use of AES will be weakened.
Interestingly with regard to (2), there is actually a (totally impractical) attack on AES that only affects the larger key 192 and 256-bit versions and not 128-bit AES - http://eprint.iacr.org/2009/317
Wikipedia _does_ put AES inside Category:Broken block ciphers.. "Widely cryptanalysed ciphers like Advanced Encryption Standard are considered stronger than un-cryptanalysed ciphers even if there are impractical attacks against them."
To be more specific: The only known things quantum computers are algorithmically superior for are factorization, computing discrete logarithms, and things that reduce to those. This happens to include all currently popular public-key cryptography. Fortunately, that is typically unrelated to symmetric-key cryptography.
At its core, to do public-key cryptography, you just need a difficult instance of an NP-but-non-P problem. Quantum computers put factorization and discrete logarithms into P, but there are still plenty of harder NP problems that have not been tapped. If quantum computing starts to become a significant threat, we'll probably see renewed interest in those.
Maybe I'm misunderstanding but if you had one of these you would have answered a fairly important question in CS theory. Perhaps you mean to say "NP-complete", but even then I'm not sure the proposition is correct.
You're right that my statement wasn't specific enough; I was going for brevity. The precise statement is: You need a problem with a known polynomial-time nondeterministic algorithm, but no known polynomial-time deterministic algorithm.
A very important point though: public-key cryptosystems rely on one-way functions, functions that are hard to invert in the average case, NOT just the worst case, which is not your typical complexity-theory mindset. So, I would be careful when talking about complexity classes in the context of crypto because it can be very, very easy to trip up and say something that's either not comprehensive or just downright incorrect.
I don't realy like rocking a boat... but quantum cryptography can't realy be used in practice.
Or, better, any practical implementation of quantum cryptography is succeptible to attacks. And the entire thing still needs an authentication method, guess what we use for authentication nowadays.
It is being used in commercial systems (e.g. idquantique). Practical implementations are prone to vulnerabilities, but none have been found that cannot be remedied. Some techniques such as device independent or measurement device independent QKD offer to make it far more difficult to come up with attacks in the future too.
The #1 advantage of QKD is not that the methods being used today will be immune to all attacks found in the future. It's that quantum states are unclonable, so there's no way to archive cipher-text for future attacks, as can be done with classically encrypted messages. e.g. If you send encrypt a message and send it via email today, the encryption method has to stand up to advances in algorithms and computational hardware for as long as the information remains sensitive. If you send something via QKD, an eavesdropper must break the protocol at the moment you send the message or it will be safe for all time.
Authenticating strangers, as in credit card transactions, is something that quantum computing may disrupt. QKD can be used safely by people who have met at some point in the past, but we probably have a bit of time before CC transactions need to be encrypted by QKD. i.e. While you should probably not send medical records or state secrets via many classical encryption protocols now, your CC info will change in a couple years so it's not as big of an issue if your transactions are cracked a few years after that.
Quantum computers have a fairly well-studied mathematical abstraction about which we can reason quite well. Algorithms for quantum computers exist which will break RSA; no similar algorithms exist to break AES.
And the link actually only applies to traditional computers; quantum computers have no analogue of destructively setting a bit, because all operations on a quantum computer are fundamentally reversible, and hence do not entail any inherent energy loss to entropy.
Public key crypto schemes (RSA, elliptic curve etc.) are vulnerable to some variation of Shor's algorithm. We'll have to move to quantum crypto when this happens. Hell for all I know D-Wave's machines can already break RSA for the DHS.
(1) We need to build computers out of something other than matter
(2) A weakness in AES must be discovered that will need to reduce the search space significantlyWe can disregard (1) as it will probably require changing (almost) all encryption algorithms that we currently use. (2) will most likely break all key-lengths so any use of AES will be weakened.