Let's follow the discussion.

assemblerex started the thread: "The universe would suffer thermal death before they break 256-bit aes."

An Anonymous Coward responded, in relevant part:

Stop citing things inaccurately enough to be a myth.

The universe would suffer heat death. Before someone cracked the encryption. Using brute force. Via exhaustive search of keyspace. Utilizing techniques currently understood by science and the present beliefs of the laws of thermodynamics. FULL STOP. Hi, Quantum Computing....you ready yet?

Another AC responded to that (emphasis mine):

**Your comparison to quantum computing is dead wrong. Quantum computers are not currently known to be useful for brute forcing any algorithm.**

**The only reason they are useful for breaking things like RSA, is that we have large number factoring algorithms that work on quantum computers (Shor's algorithm).** RSA was known to be vulnerable to large number factoring from the moment it was designed. In fact, as a one way encryption function, that's part of it's design. We assume that problem to be "hard", but with large enough quantum computers we can make it "easy". Brute forcing RSA was never considered as factoring the modulus is already more than an order of magnitude easier.

**AES does not rely on a one way mathematical function for security, so talking about quantum computers breaking it is just silly. Weaknesses in the algorithm itself are the biggest threat to it.** Your points about entropy per character are also rather silly as that's an implementation issue and has nothing to do with the AES algorithm. Also for the record, the character set of all keyboard enterable keys is about 6.6 bits of entropy with a random distribution. No idea where you got 4.24 bits from, but even random lowercase letters alone have more entropy per character than that.

assemblerex's point remains valid. **Until computers are build from something other than matter, or occupy something other than space, it is unlikely that we will be "brute forcing" 256-bit keys.**

It's certainly up for debate what the first AC meant, but it's quite clear what the second AC meant: **quantum computers do not usefully improve our ability to use brute force to break AES or anything else**. Further, it's clear that the AC is claiming this lack of usefulness for brute force alone, using the example where factoring, a non-brute-force approach, is usefully improved by quantum computers. The AC is not saying that factoring is the only such possibility. I don't think I'm reading anything into this, but let me know if I am.

This is relevant because it was to post to which you initially responded, writing:

You seem to be assuming that brute-forcing is somehow a difficult computational task for quantum computers, as opposed to some factoring algorithm. On the contrary, it is trivially easy: all it requires is the incrementing of a counter.

But of course AES itself would actually have to be implemented in the quantum computer, or you lose any advantage that quantum computing might give. That would be the hard part. But as it's a straightforward and known algorithm, I don't see any particular difficulty.

Quantum computing is Turing-complete, so there is no theoretical reason that it could not be done.

Particularly in the context of the post you're replying to, it is reasonable to assume that you meant that brute forcing AES on a quantum computer would be usefully faster, maybe to the point of being feasible, not merely the trivial point that it's possible given unlimited running time.

I responded, linking to Grover's algorithm:

Um, no. The speed-up is quadratic, so it's no easier than classically brute-forcing half the key length.

The point is that Grover's algorithm is the optimal way to find a brute force match on a quantum computer, that it is quadratic faster: O(N^(1/2)) rather than O(N), and that therefore with an n-bit key, which would be O(2^n) to brute force on a classical computer, on a quantum computer it is O((2^n)^(1/2))=O(2^(n/2)), which is the time to classically brute force half the key length. Certainly this is sometimes a big deal, but it's not very helpful if the original n is 256, because 2^128 is still impractically large.You can see that this paragraph matches the statement in my post--I'm elaborating for your benefit, not "waffling."

Note: this optimiality is of course even if you can implement AES as a quantum algorithm--otherwise you can't even use Grover's algorithm. Fortunately, quantum computers are Turing-complete, so this is not a problem. (Also, BQP is a superset of P, so there is no super-polynomial slowdown.) Also realize that I'm only worried here about theoretical limits of quantum computing , not engineering limits. I apologize if this wasn't clear, but it seems like it would only help you if I'm only worried about theoretical limits...

You could have taken the opportunity to clarify that you didn't really mean quantum computers could feasibly brute force AES-256, but instead you made several posts about parallelism.

I was not referring to Grover's algorithm. I was referring to quantum computation in general. That same article says about Grover's algorithm: "It provides a quadratic speedup, unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts."

Further, that is merely the "speedup" (in big-O terms, not absolute terms) of the algorithms that come from using qubits for computation rather than classical binary computing. It has little relationship to actual "speed", especially when you factor in the potential for massive parallelism.

To clarify what I mean: obviously, something on the order of O(N^1/2) is going to be more efficient than, say, O(logN) or worse O(N^2). However, if you have a million or more fast processors working on the problem in parallel, even O(N^2) or worse may be doable in realtime. So in the quantum realm big-O order alone does not dictate practicality.

Pardon the multiple posts, but I have kept thinking of what seem to me to be better ways to explain what I mean.

Imagine you have a problem of O(N^2) [which is pretty bad... brute-forcing is at worst linear, averaging O(N/2)].

If your algorithm can dedicate N^2 processors to the problem, then in effect, that is to say in realtime, the majority of your computation time will be taken up setting up the problem. The solution will take a very short time. So if you have an efficient way to set up the problem, the solution is a microsecond away. Obviously there is a tradeoff here, and more research needs to be done.

I realize that is an extreme example, but there is nothing in theory preventing it. So if you can find a way to quickly and efficiently set up qubits to perform boolean or the equivalent logic in parallel (which has been done on a small scale), many of what are today prohibitively time-intensive computational tasks should fall like dominoes.

From my perspective, you were clearly not backing down from the idea that quantum computers could feasibly brute force AES. I assumed that you meant that quantum computing provides a parallelism beyond that provided by classical computers, which brought me to the assumption that you believed that quantum computers can "split the universe" and do things in parallel. I apologize for making that assumption and putting words in your mouth. However, given that a factor of "a million or more fast processors" means jackshit when you're talking about 2^128 or 2^256, you can understand that, missing that part, I assumed you meant the sort of massive "splitting the universe" parallelism that would make brute forcing AES feasible. I currently don't know what your point was with the parallelism.

Anyway, I then wrote:

I'll just respond to all your posts at once. There is a section "Optimality" in the Grover's algorithm article. You should read it. (And please don't bother bringing up the point that it that article says that it is not proven that NP is not contained in BQP. Lots of things aren't proven, but if P=NP there is no encryption anyway.) In the field that people refer to as quantum computing, there is not, and almost certainly cannot be, any generic procedure to get exponential speed up.

In response to points you brought up: (1) This whole notion that quantum computing is the same as classical computing with extremely massive parallelism is grossly incorrect, whatever lay magazine article you read notwithstanding. (2) Specifically, uantum computing does not change the fact that you cannot have 2^256, let alone (2^256)^2, processors in the physical universe (you do not get a number of generic "processors" that is exponential in the amount of matter you have). (2) **Some** algorithms may be exponentially faster with quantum computing, but you were obviously claiming that **every** encryption algorithm can be brute forced, presumably subexponentially, by a quantum computer, which is a completely different claim.

It is a common fallacy to believe that there is rational expectation that quantum computing can brute force everything. Regarding Arthur C. Clarke, don't be a jerk. The frame of discussion has clearly been the current scientific field of quantum computing. When you said that "brute-forcing" is "trivially easy" for quantum computers, the assumption is that you have some actual reason to believe that is true, not that you're speculating about technology in the future that goes beyond current theory. Telling you that you are wrong is simply stating a correct fact about the field of quantum computing--it is not a claim that technology beyond this is a priori impossible.

I stand by my statement that you were saying that quantum computers could feasibly brute force everything. There was nothing specific to AES. You did attach some importance to creating a quantum implementation, but as you seemed aware, this is just an engineering issue. Furthermore, the very nature of brute force is that the algorithm is treated as a black box. If you can feasibly brute force algorithm A over N possibilities, where trying each possibility uses an amount of reasources X (time/space/power/whatever), you can feasibly brute force algorithm B over N possiblities, where trying each possibility uses an amount of resources comparable to X. If this isn't so, you weren't brute forcing A in the first place: you were using some special property of A. If quantum computers can feasibly **brute force** AES-256, then Blowfish-256, Serpent-256, and so on, will "fall like dominoes".

Regarding the "lay magazine" reference, I again apologize for assuming you were thinking of "split the universe" parallelism.

On to your last posts.

First, I want to repeat that I was NOT referring to Grover's algorithm. Nor, for that matter, did I claim that there is a generic procedure to make any algorithm exponential. (Which is a rather ridiculous statement on its face: if any algorithm could be made exponential, then why isn't Grover's?) What gave you the idea that's what I meant? It's not in anything I wrote.

You can't have been referring to anything better than Grover's algorithm, as it's the optimal way to brute force with a quantum computer. My belief that you believed that there is a generic procedure for exponential speed-up (of classical algorithms only, certainly I would not have thought you had some ridiculous belief that quantum computers can speed up quantum algorithms and thereby run infinitely fast) is because of your implication that quantum computers might feasibly brute force AES.

Now, for the numbered points: (1) [] (2) []

(1) I apologized about the "split the universe" assumption. (2) I remain currently in ignorance of what your point is with the parallelism.

(3) Where in the world did you get the idea that I was **claiming** that "every" encryption algorithm could be "brute forced"? Much less "obviously" claiming that? That is such a gross mis-reading of anything I wrote, I have to wonder whether maybe you were watching TV at the time and only reading every other word or something.

Explained above. If "brute force" applies to AES but not similar things, it isn't brute force.

The concept that I was trying to get across was that if you did have large-scale parallelism, quantum versions of the classical algorithms -- even after optimizing the algorithm for operation with qubits -- may not turn out to be the most efficient approach. I felt this statement was pretty clear: "*So in the quantum realm big-O order ***alone** does not dictate practicality." [emphasis added] Apparently I should have explicitly stated "big-O order *of the classical algorithm* does not dictate practicality." I felt that part was implicit given the context, but maybe not.

Again, we're talking about brute forcing. Each individual operation of trying a key is O(1) -- the speed of the AES implementation itself is just a constant factor so it's not really relevant to the discussion. If you're doing something that takes advantage of details of the algorithm to do better than the O(N^(1/2)) you get with Grover's, then you're not brute forcing--you're using a weakness in the cipher.

As for your last paragraph, you are far out of line. First, once again, I did not say or even imply that **anything** can "brute force anything". Who's being a jerk here? How arrogant. Apparently you don't even know what "brute forcing" is, in the context of an encryption method (and I never mentioned "brute forcing" in any other context!). Otherwise you wouldn't be accusing me of "obviously" saying that "quantum computing can brute force anything"... which is not even close to what I wrote. So you are showing your ignorance of the subject, or you were grossly misinterpreting my words, or both.

Please explain why you'd be able brute force, for example, AES-256 but not Blowfish-256.

Here's a little lesson for you, just as a freebie (I certainly don't think you deserve it): "brute forcing" means trying all possible keys against an encryption. It doesn't mean trying all possibilities of the plaintext, or anything else like that. So in the classical scheme brute forcing is a strictly linear O(N) function of the size of the encryption key. In fact, given random distribution of keys, the solution will average N/2. As long as you have an implementation of AES to work against, then, all brute forcing requires is a simple counter to be incremented, to generate the possible keys. **Which is trivially easy!** And the keyspace can be divided into smaller parts **and worked in parallel**. Are you beginning to understand now? And don't come back claiming I am waffling: I clearly stated that you would need a quantum implementation of AES to work against. We all know that is beyond our present capability... but we also all know (or should) that it is **theoretically possible**, also exactly as I stated.

So let's just be clear: I made no claim that quantum computing could instantly solve all our ills, or "brute force anything", or solve all NP-complete problems (much less, efficiently). The single concrete example I gave of what I meant was a problem with a known (classical) linear solution and a keyspace that may be large, but is definitely finite and lends itself well to parallel solving.

I have adequately explained how you implied that quantum computing could feasibly brute force AES, as you seem to acknowledge in the last sentence. As I've said, parallelism means jackshit when you're talking about 2^256, even if each computer can use Grover's. If there's some point beyond that with the parallelism, you've never said.

And since you mentioned "...whatever lay magazine article you read", then used the hypocritical tactic of calling on Wikipedia, of all things, for your source, and you apparently want me to write of specifics, instead of just giving illustrative examples, here's an FYI: Wikipedia itself says that quantum computing is an ideal candidate for many kinds of decryption, and that we already know how to adjust **classical** "brute forcing" algorithms for encryption systems like AES for quantum computing so that it would work not in O(N^2)... or even O(N)... but in O(N^1/2)!

Uh, yeah, that O(N^(1/2) was the reason my very first post said, "it's no easier than classically brute-forcing half the key length". In fairness, maybe you were watching TV at the time and only reading every other word or something.

And you **completely** missed my point that the classical algorithms may not, in the long run, turn out to be the most efficient way to go. There may turn out to be better approaches. For example there is a recent, new technique that reduces the keyspace significantly.

If you're talking about cryptanalytic attacks on AES, that's **not brute force**. I gave the best possible quantum algorithm for brute force search in my first post.

So... I am tempted to **repeat** my quote of Arthur C. Clarke. Jerk.

Make no mistake, we're both arrogant bastards.