Microsoft Backs Laws Forbidding Windows Use By Foreigners

According to Groklaw, Microsoft is backing laws that forbid the use of Windows outside of the US. Groklaw doesn’t say that directly. Actually, they pose charmingly with the back of the hand to the forehead, bending backwards dramatically and asking, “ Why Is Microsoft Seeking New State Laws That Allow it to Sue Competitors For Piracy by Overseas Suppliers? ” Why, why, why, o why, they ask.

The headline of this article is the obvious reason. Microsoft might not know they’re doing it for that reason. Usually, people with the need to do something, dammit because they fear they might be headed to irrelevancy think of something and follow the old Aristotelian syllogism:

Something must be done.
This is something.
Therefore, it must be done.

It’s pure logic, you know. This is exactly how Britney Spears ended up with Laurie Anderson’s haircut and the US got into policing China’s borders. It’s logical, and as an old colleague used to say with a sigh, “There’s no arguing with logic like that.”

Come on, let’s look at what happens. I run a business, and there’s a law that says that if my overseas partners aren’t paying for their Microsoft software, then Microsoft can sue me, what do I do?

Exactly right. I put a clause in the contract that says that they agree not to use any Microsoft software. Duh. That way, if they haven’t paid their Microsoft licenses, I can say, “O, you bad, naughty business partner. You are in breach of our contract! I demand that you immediately stop using Microsoft stuff, or I shall move you from being paid net 30 to net 45 at contract renegotiation time!” End of problem.

And hey, some of my partners will actually use something other than Windows. At least for a few days, until they realize how badly Open Office sucks.

Ambrose Bierce Punks Richard Feynman

Via Boing Boing, where Maggie Koerth-Baker gave a delightful pointer to this film of Feynman explaining for seven-and-a-half minutes why he can’t really explain why magnets repel each other. Or attract, either.

And trumping him in time and space, Bierce gave us this in 1906:

MAGNET, n.
Something acted upon by magnetism.

MAGNETISM, n.
Something acting upon a magnet.

The two definitions immediately foregoing are condensed from the works of one thousand eminent scientists, who have illuminated the subject with a great white light, to the inexpressible advancement of human knowledge.

Quantum Crypto is Quantum Backdoored, But It’s Not a Problem

Nature reports that Quantum Cryptography has been completely broken in “Hackers blind quantum cryptographers.” Researcher Vadim Makarov of the Norwegian University of Science and Technology

constructed an attack on a quantum cryptography system that “gave 100% knowledge of the key, with zero disturbance to the system,” as Makarov put it.

There have been other attacks on quantum cryptography, but this is the first in which there is no indication that the key has been stolen. In those attacks, the operator of the system would see the transmission error rate go up, but in Makarov’s attack, the operator sees nothing. In short, they are completely, utterly defeated. The attacker gets everything with impunity.

As usual, the quantum crypto crowd doesn’t see that a 100% loss of key with no inkling of the loss is a problem. Makarov himself said to Nature, “If you want state-of-the-art security, quantum cryptography is still the best place to go.”

Perhaps the kicker is this in Nature’s article:

Ribordy [CEO of ID Quantique] and Zavriyev [Director of R&D at MagiQ] stress that the open versions of their systems that are sold to university researchers are not the same as those sold for security purposes, which contain extra layers of protection. For instance, the fully commercial versions of IDQ’s system also use classical cryptographic techniques as a safety net, says Ribordy.

Huh? We can trust commercial versions of quantum crypto because it uses classical crypto as a safety net? That’s saying that the quantum coolness is really just icing over a VPN. Isn’t it? Am I missing something?

Now it’s time for a rant. Quantum cryptography is really, really cool technology, but the whole point of it is, well, security, and if the state of the art is that the system is breakable, then the art is in a sorry state. It’s a state of being a research toy, not a real security system.

The whole point of quantum crypto is that it isn’t even really crypto. It’s communications that can’t be eavesdropped on. It’s a magical tour-de-force of science and technology. But if it can be silently thwarted, it’s no good. If there is no way that it can be tested to be good, it’s no good. Moreover, the latter is more important than anything else.

For quantum crypto to be viable and trusted, we have to have some way that we know that the boxes were designed and manufactured in such a way that we can be confident that there’s no silent quantum backdoor in the box, then it has no value. You might as well just get a VPN router from the usual suspects and be done with it. If you’re really paranoid, just lay down some glass fiber and put it in a conduit.

Quantum information science as a discipline needs to start taking security seriously. It can’t just brush off a break of this magnitude, and remain credible. Come on, at least admit this is serious and has to be reflected in the manufacturing and testing. Come up with countermeasures, something.

P != NP and Security

There’s been a lot of discussion about the paper written by mathematician Vinay Deolalikar on this interesting problem.

The P!=NP problem is so interesting that there’s a million-dollar prize for solving it. It might even be interesting because there’s a million-dollar prize for solving it. It might also have some applicability to computer science and even cryptography. The August 11 edition of Deolalikar’s paper can be found here.

Because this is an interesting problem, there’s a lot of pressure on domain experts and pseudo-experts to comment. I classify myself as more pseudo-expert than expert, so color your filters accordingly.

Among the real experts, my favorite is Scott Aaronson, who is an expert in complexity theory and quantum information science. If you aren’t completely clear on the whole thing, his essay, “P vs. NP for Dummies” is a good place to start.

His essay, “Putting my money where my mouth isn’t,” is a marvelous snap response. In it, he says that he’s willing to contribute his on $200,000 to the million-dollar prize, should this proof be right. He gives some great reasons for his own snap commentary and his own decision not to cancel his vacation to look at the paper.

Aaronson also points to his own essay from 2008, “Ten Signs a Claimed Mathematical Breakthrough is Wrong,” which you should be reading before you read anything about Deolalikar’s paper. It’s not about Deolalikar, it’s about the general issue of breakthrough papers of any sort.

But getting back to this particular paper, there’s a lot of skepticism, and a good summary of the skepticism comes from Terence Tao.

I’ll add in my own raised eyebrow along with my own general discussion of P!=NP. I have three points:

  1. P!=NP really isn’t interesting.
  2. Most comments about the whole P vs. NP don’t understand the ramifications of it, especially when dealing with practical disciplines like computer science and cryptography.
  3. The reason I have a raised eyebrow centers around those two above.

So here we go.

P!=NP really isn’t interesting. What would be interesting would be if someone proved that P=NP. We all expect that P!=NP, we act as if it’s true. On the one hand, that means I’m far more likely to believe Deolalikar because he’s proving that which we expect to be true. On the other hand, that means it’s harder evaluate his proof because it is proving something we all think is true.

Understanding P vs. NP. Conventional wisdom about P and NP often includes thoughts such as, “The implications of this [P=NP] on applications such as cryptography, and on the general philosophical question of whether human creativity can be automated, would be profound.” I disagree. I think that if it turns out to the shock of everyone that P=NP, it will be a yawn.

Let’s suppose that P=NP, which means that a large class of problems have solutions in polynomial time. Great. That doesn’t mean they’re easy to solve. It doesn’t mean that the solutions are even useful.

Here’s an example. A few years ago, we got a polynomial time primality test algorithm, the AKS test (named for its authors, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena). Originally, it was an x12 algorithm, and everyone needing primality testing ignored it, because that’s too slow. It’s been improved to x6, which is still too slow. It’s polynomial, but that doesn’t matter.

In practical terms for cryptography, let’s suppose you want to generate a 2048-bit RSA key. For that, you need two 1024-bit primes. Right now, the tests that we use are “probabilistic.” I put quotes around it because while there’s no guarantee that the number that passes the probabilistic test is actually prime, no one has ever (knowingly) found a number that passed the probabilistic test and was not actually prime. In fact, if you found such a number, it would be a result worthy of publication. Thus, the risk of the inexact test is very low. But the cost of the exact test is 10246 which is a very large number, 1,152,921,504,606,846,976, and we can’t really afford that.

Thus, for this function that’s useful for crypto, primality testing, we know that there is a P solution, x6 is too large a P. The fact that it is P turns out to be uninteresting.

For the purposes of cryptography, even x3 is probably not good enough. Some time ago, I harumphed about quantum computers doing factoring, and much of my harumphing boils down this observation — that even a low power polynomial like a cubic may leave the advantage to the code-maker over the code-breaker.

This is why I think that if P=NP, it could still be a yawn. If you find a polynomial solution with an exponent of somewhere in the 3-10 range, they are so hard so fast that the fact that the solution is polynomial is a merely a factoid. It seems a good bet that if there were a quadratic-scale algorithm for factoring, we’d know it.

This is a subtle point, so I’ll make it one more time. If P=NP, it’s only interesting if the polynomial is of low order. Polynomial-time problems can easily be intractable.

If it turns out that a bunch of cryptographic problems are polynomial, but order x6 or more, then the cryptographers aren’t going to lose a lot of sleep. In fact, they’ll have a good reason to get everyone to upgrade all their software, and that will be pretty much the end of it.

On the flip side of this, most NP-complete problems we know about are not as hard as we’re led to believe. The most famous NP-complete is the Traveling Salesman Problem. While it is indeed very hard to come up with the shortest solution for arbitrary problems, it’s actually very easy to come up with acceptable solutions for reasonable problems. Heck, it’s not like actual traveling salesmen have lots of problems covering their routes. There is even a nice web page that computes routes on Google Maps. I think a good way to put this in perspective with the P vs. NP problem is to note that there is a prize for solving a 100,000 city problem, and that prize is $100.

Most of the genuine hard problems we have are only hard to solve on edge conditions. There are many attempts to create cryptosystems out of real NP-complete problems, and their track record is pitiful. We really don’t have any of them. I say “really” because we have one — lattice cryptography — and it still has issues. It’s slow, big, and complicated with intellectual property. Worse, some forms of lattice cryptography have had problems similar to the Traveling Salesman Problem. The GGH cryptosystem has the flaw that all ciphertexts leak information about the plaintext. Oops.

The bottom line here is that many problems that we know to be hard are easy in most cases and that “easy” problems might still be hard enough that they’re useful for protecting secrets. Whether P=NP or P!=NP is something that is interesting to mathematicians and philosophers far more than to scientists and engineers.

Raised eyebrow department. Now I get to why I’m so far skeptical. The quote that I gave above about what it would mean if P=NP comes from Deolalikar’s paper. Perhaps naïvely, I expect an expert on complexity theory to go beyond the usual science-reporting ooo-ahhs. I expect a complexity theorist to understand that complexity is complex, or at least subtle. I’m not a complexity theorist, I’m a mere complexity practitioner and I understand that complexity is hard to understand.

However, he’s right. If P=NP, it would be a deep discovery and have philosophical import. However, however, he’s proved the opposite, and so discussion about what it would mean if his proof were out of phase with what it actually proves seems weird.

Fine, fine. Everyone’s entitled to their soapbox, particularly when they do something significant. But reading through the proof there’s something missing. In brief, his proof has to prove that something that everyone thinks is hard is in fact actually hard. Ironically, this is harder than proving that it’s actually easy (which is again the proof of the opposite thing). Part of proving that something is hard ought to include showing that a related problem is easy.

In the P vs. NP world he’s chosen, he is showing that 3SAT is hard. 3SAT, to oversimplify, looks at the combinations of three boolean operations, such as A or B and C. 2SAT (combinations of two boolean operations) is known not to be hard. Had Deolalikar shown that 3SAT is hard and 2SAT is easy, I think we’d all be wowed. With only half of that, we’re left hanging and scratching our heads. Since we expect 3SAT to be hard, there needs to be some contrast against a related known easy problem for contrast. Without that contrast, it’s very hard to value the proof.

Worse, if one were to take his proof mechanism and apply it to 2SAT and come up with a conclusion that 2SAT is also hard, then there’s a huge hole in the proof. If I were analyzing the proof, I would in fact start by seeing how it applies to a few known-P problems. If it proves they are NP, we have a problem.

To sum up, I bet the proof doesn’t hold up because it only addresses the wheat, not the chaff. Any prover of P!=NP has to deal with the problem that we expect that to be true and that it’s hard to prove that something we think is hard actually is hard. Disproving it is easier in the sense that if you come up with an easy solution to something everyone thinks is hard, it is — um, well — hard to argue with that. Without some contrast, any proof of P!=NP looks on its surface as if you’re saying, “Hey everyone, you know that problem no one can easily solve? I can’t easily solve it, either!” That lacks intellectual force.

Nonetheless, maybe he has it. Maybe in a few months we’ll all be wowed, once it sinks in. Heck, maybe he doesn’t have it this summer, but next summer a revised proof will have us all cheering. Only time will tell. But right now, it’s interesting but unconvincing.

My personal bet, which I have no proof for, is that P!=NP is true but unprovable. I’m holding out for the proof that it’s unprovable.

Ridiculing the Ridiculous: Terrorist Tweets

A group of soldiers with the US Army’s 304th Military Intelligence Battalion have managed to top previous military research on terrorist use of World of Warcraft.

Realizing that mentioning the word “terrorist” can allow researchers to acquire funding to play the popular MMOG, they turned attention to the popular, if architecturally unscalable micro-blogging system, Twitter.

Surpassing the threat-analysis skill of super-spy Chad Feldheimer from the recent documentary “Burn After Reading,” they mention not only the threat of “socialists,” “communists,” and “anarchists,” in using Twitter to “communicate with each other and to send messages to broader audiences,” but the wider and more up-to-date threats from “religious communities,” “atheists,” “political enthusiasts,” “human rights groups,” “vegetarians,” and last but not least, “hacktivists.” They notably left out delinquent teenagers, so one presumes they don’t use systems like Twitter.

The Military Intelligence group also discovered that people can use GPS in phones like the Nokia 6210 and Nokia Maps to know where they are. This could let terrorists who want to illegally cross a border know where that border is, or to know that a certain large triangular stone thing is the Pyramid of Cheops (category: Attraction).

The report’s cutting edge thinking also discusses how terrorists could use voice-changing software such as AV Voice Changer Diamond to make prank phone calls and effectively hide under an abaya.

The full report, marked “For Official Use Only,” can be found here. It also redacts with a dark gray splash of ink the email address of sarah.e.womer@ugov.gov, from whom you can get a copy of the report if you do not have access to INTELINK, Cryptome, or the Federation of American Scientists.

I think the report speaks for itself. I just can’t make this stuff up, apart from the bit about hiding under an abaya.

Elections Are Done For Me

I Think I Voted

Forty Percent of California voters are “permanent absentee” voters. Oregon runs entirely by mail-in votes. Other US states have some sort of mail-in or absentee status that people can assign themselves to.

For those people, including me, elections are a slice of time that ends on election day. This isn’t new, until relatively recently, it all worked that way. You couldn’t expect everyone to all be in town on that one day. It is only urbanization that allows us to have elections be an event rather than a process. I sat down last night and waded through the whole mass of offices, measures, and initiatives. I have now completed my civic duty.

This is probably a good idea, as many of the issues with voting and counting votes and securing them have in their model that it has to be done on one day, and as quickly as possible after the polls close. It improves security and accountability to allow and encourage people to vote over an interval of a few weeks.

Emergence Emerges

This paper, “More Really is Different,” may be one of the most important papers of the last half-millenium. It argues that P.W. Anderson’s concept of “emergence” is provable. It may have even proved it.

The idea of emergence, from whence this blog gets its name is the opposite of reductionism. It is the idea that a complex system acquires properties that the underlying parts cannot predict. It’s nothing more and nothing less than a formalization of the adage, “The whole is more than the sum of its parts.”

The authors, Mile Gu, Christian Weedbrook, Alvaro Perales, and Michael A. Nielsen, argue directly that this may mean that a “Theory of Everything” may therefore be impossible.

This is big, big news. Read the paper. Read the commentary in The New Scientist, “Why nature can’t be reduced to mathematical laws.”

If they are right, this goes to the core of the philosophical underpinnings of the way we understand the world. It may help explain everything from weather prediction to the origins of life to whether souls exist. I might even be engaging in understatement rather than hyperbole on that last bit. You may think it’s a long way down to the chemist’s, but this is big.

While you’re at it, expect some highly entertaining debate, and pseudo-scientific whackos of every stripe to start quoting this. Maybe the next Kuhnian revolution has begun.

Death Penalty Protestors are Terrorists

The Washington Post reports upon the further cheapening of the word “terrorism” in, “Md. Police Put Activists’ Names On Terror Lists.”

The fifty-three people with “no evidence whatsoever of any involvement in violent crime” who were put on a list of terrorists include anti-death-penanty protestors.

It’s really hard to keep from laughing about this. Are we going to see next, Terrorism With Intent to Kill, so as to differentiate it from Terrorism With Intent to Stop Killing? Whatever your feelings about the death penalty, this ain’t terrorism, guys.

The Post reports a number of things Police Superintendent Thomas Hutchins said that he’ll be ashamed of once the meds kick in.

After “stunned” state senators called him to task about the spying, Hutchins said:

I doubt anyone who has used that term has ever met a spy … What John Walker did is spying.

Please don’t make me paste in dictionary definitions, Mr Hutchins. Quoting the dictionary is the last refuge of two-bit pedants and I’m at least a sixty-four-bit pedant. The Maryland committee you embarrassed yourself in front of has in fact seen a spy. If you need help, I recommend a mirror.

Hutchins also said that some of the names might have been shared with the NSA as well. Might have. That’s “might” meaning “definitely,” I presume. If you’re going to spy on peaceful protestors, but them on terrorist lists, and share that with the intelligence agencies, have the courage to say so.

Here’s a final quote from the Post:

Two senators noted that they had been arrested years ago for civil disobedience. Sen. Jennie Forehand (D-Montgomery) asked Sheridan, “Do you have any legislators on your list?” The answer was no.

That’s how we know they knew it was wrong.