top
### Alternatives To Paypal's Virtual Credit Card Service?

I'm not convinced that you understand how credit cards work, or for that matter, how money works.

And I think you're being willfully obtuse.

Doesn't matter if it's your bank or your credit card company, it's YOUR money that's gone. With a debit card the money comes out of your bank, with a credit card the money initially comes from the credit company, who sends you a bill, and you send them money from your bank. In either case you can file paperwork claiming fraud, and in both cases a valid claim of fraud will result in your money being returned. (specific policies vary by company and bank)

When you receive a bill, there is no force of nature causing you to send payment. Here's how it works with a debit card:

- Money is stolen via your card, coming immediately from your bank account.
- You notice the discrepancy (perhaps because you want to withdraw money you expected to have but don't, in which case it sucks to be you).
- You ask the bank to return or restore the money, claiming fraud.
- (a) The bank returns the money, or (b) the bank denies the claim.

In case 4(a), you have no access to the money in the time between 3 and 4(a), which could be 10 business days (two weeks). In 4(b), it is up to you to pursue legal action against the bank.

Here's how it works with a credit card:

- Money is stolen via your card, being paid from the card company's accounts.
- You receive a bill including the fraudulent charge (note: the company is asking you for money, rather than vice versa).
- You make a claim for fraud.
- You send a payment only for the non-fraudulent amounts.
- (a) The company accepts your claim, and that's the end of it, or (b) they deny your claim, so you keep getting bills and other collection action.

In 5(b), it's up to the company to pursue legal action against you, rather than vice versa. In all cases, the money remains in your control at least until the company wins in court. (Of course, you would lose the money with the debit card as well if you lost against the bank in court, but the money would have remained out of your control immediately.)

The point is clear: your money is gone with a debit card in that you lose actual control of it, and have to ask for it back. The card company's money is gone with a credit card because they have to ask you for it back (perhaps not entirely, if they haven't paid the merchant yet, but that's not your concern).

top
### FBI Failed To Break Encryption of Hard Drives

That was how it was used by both Bruce Schneier and RSA themselves in articles about the subject. I'll go with their usage. I realize that in a way that is "appeal to authority", but in this case there is little doubt that they are greater authorities on the subject than you or I.

Argggh. However, I think I'm right at least as to symmetric ciphers. I've never heard brute force refer to anything that doesn't treat the algorithm as a black box in that case.

No, it isn't. I know what a theory is, and so do you. The difference is in the phrase "currently known". It **is** "currently known" that **in theory** (real theory, you have yourself written about it) quantum quantum computing could be quite useful in brute-forcing some systems. In that respect the sentence I quoted is just plain incorrect. If it was meant in a different way, it should have been written in a different way. I will concede that it may not be "currently known" to be useful against AES-256 and the like, but the sentence clearly says "any algorithm", which is just as clearly (ref: sources we have already discussed) incorrect.

It is true that there is a sweet spot in key length where brute force by a classical computer is infeasible but by a quantum computer it is feasible in theory. What people usually mean by quantum computers not being useful for brute force is that, for any algorithm with adequate choices of key length, where the time is linear in key length or close to it, if key length N is infeasible for classical computers to brute force and you're worried about quantum computers, you can simply choose 2*N. (I have no reason to think you disagree with these statements, I'm just saying what people probably mean.)

And that's all fine, but that isn't the way I was using the word. At least I never meant to use it that way. If I have, please refresh my memory. [...]
So wherever the "blame" lies, if such there be, we do not disagree so much after all. It was more of a communication problem than anything else.

I sure as hell do not plan on reading through again to figure out the blame and/or argue about it.

There is no sound basis today for saying we "know" how to do the most efficient quantum computing, even in theory. We don't even know how many different types of particles there are, or their properties!

The problem is the way physical laws are updated with new knowledge. Nineteenth century physics was correct in normal human situations. We know at least it was wrong at the samll scale, high speeds, or high gravity. It was the small scale issues that were technologically revolutionary (e.g., semiconductors and probably quantum computers at some point), because there are no inherent resource problems with building small things. Currently, QM really looks correct at normal small scale situations. Where things break down is high engergies and also high gravity is still not solidly understood. So, this is all very exciting for physics, but we won't end up with a Tevatron on everyone's desk. It's pretty clear I consider new computing due to new physics more science fictional than you (although it's clearly possible). Thus, I'm not inclined to say it has to be related to QM as opposed to small black holes or wormholes or the like.

top
### FBI Failed To Break Encryption of Hard Drives

It is true that I was writing under the assumption that when brute-forcing, the encryption algorithm (assuming it can be implemented at all) is pretty much irrelevant (black box). But it is not. A encryption with a 512-bit key has indeed been brute-forced (about 7 years ago), but I wasn't accounting for the fact that it was RSA and weaknesses in its keyspace were exploited.

Well, I have to admit that people use "brute force" that way, but that's only because people use "brute force" loosely. They didn't try all 2^512 private keys: they factored the public key, and they didn't even use a brute force factorization like trial division! Nothing about that is brute force--it's just an instance of people using "brute force" to mean "best known attack".

This statement is pretty much irrelevant, because regardless of what THEY were saying, I clearly stated that I was referring to theory, not "current" capabilities. And really, even in any possible context being dealt with here, that is an asinine thing to state, because if we are really discussing our capabilities now, TODAY, then we are capable of very damned little, and almost nothing that has been discussed in this thread is even feasible. There would be little point in having a discussion at all.

I said I'm not talking about what's possible with current engineering limitations, which would indeed be pointless. It's pretty obvious that we're talking about different things by "theory". I tried to clarify that in response to the Arthur C. Clarke quote. I'll do so more fully. One sense of "theory" in the future unknown, where everything is possible except traveling faster than light, and maybe even that is possible. I consider this equally pointless. Sure, we might feasibly brute force AES using a quantum phenomenom uknown to current physics, but we might also break it with something unknown to physics that has nothing to do with quantum mechanics.

My sense of "theory" uses the fact that we have a mathematically well-defined theory of quantum computing at this point, in addition to actual physics research about building the things. For example, there's a complexity class BQP, and it doesn't change anything about the class if we discover that a new type of computation is physically possible (although it creates a naming problem if this also involves quantum mechanics), just as harnessing a physical phenonmenon to solve NP-complete problems in polynomial physical time would not prove that P=NP. This provides a useful basis for discussion. We can think about what might happen if decoherence problems are solved, and systems with hundreds, or thousands, or that matter billions of qubits are built. And, to continue with our current example, we can say that overcoming practical problems like decoherence is not itself enough to brute force AES. This talk about theoretical limits is thus useful, just as speculation can be. The only disagreement I continue to have is what I identified above: there's no reason to say that newly discovered physical possiblities allowing faster computation will be quantum in nature.

top
### FBI Failed To Break Encryption of Hard Drives

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.

top
### FBI Failed To Break Encryption of Hard Drives

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.

top
### Quant AI Picks Stocks Better Than Humans

Take a look at the Dow Jones average over the past 30 years. Take note of how in the past 12 it has huge fluctuations. The current system of trading stocks is broken. The market moves so fast it is all in the hands of computers. It needs to slow down.

This is an artifact of using a linear scale, so that a 10% fluctation when the index is 10,000 is much larger than when it is 2,000, and the fact that the market has, in retrospect, stagnated for the past decade.

Here is linear plot of the DJIA for the past 30 years: 1980 to 2010 linear

Here is a linear plot of the DJIA for 1949 to 1979: 1949 to 1979 linear

I don't think that algo trading started in the 1970s, ceased from 1980 to 2000, and then resumed. Of course, there is still more contrast between the 2000s and the previous two decades than between the 1970s and the previous two decades. This is because in the latter case the market increased about 4 or 5 times to get to the level where it stagnated, while in the former it increased 10 times, so the effect of earlier years being muted in a linear scale is stronger. In particular see the market lose and regain 40% of its value from 1973 to 1976. The past decade is not unprecedented.

The correct way to look at this is with a logarithmic scale. Unfortunately, the graphs I have are vertically compressed in a log scale, but you can still compare the fluctuations in the last ten years of the graph to the fluctuations in the first twenty years of the same graph. Coincidentally, in each graph there is a large dip at or near the end, due to actual recessions.

Here is a log plot of the DJIA for the past 30 years: 1980 to 2010 log

Here is a log plot of the DJIA for 1949 to 1979: 1949 to 1979 log