Quantum Debate

The debate about Shor’s Algorithm (which I blogged about a couple days ago) continues. Rod Van Meter has a good blog post about it here.

While there are plenty of people who have just wholesale dismissed the Hill/Viamontes paper outright, apparently because they know Shor’s algorithm works and that building a working quantum computer is obviously merely a matter of making some qubits, Van Meter is more to my thinking about the whole thing.

I have read it, but not studied it in major detail yet. I don’t know either of the authors personally, but the second author has done good work; he is certainly no dummy.

The argument is pretty straightforward, arguably naive. That doesn’t mean it’s wrong, but there are a lot of assumptions and simplifications in the work, and they need to be examined carefully.

He also says:

Anyway, I hope this at least short-circuits any rush to burn Peter Shor in effigy. He’s way too smart and sweet for that.

Here’s where I think I need to rant a bit. I’m certainly not calling for anyone to be burned in effigy or reality. I can’t testify to how sweet Peter Shor is, but I agree that he’s brilliant and I admire him.

However, Leibniz was also smart and worked in the forefront of calculation as well. His calculator had issues with propagating carry with two-digit or three-digit multipliers. That doesn’t make Leibniz any less brilliant or his achievements any less.

Peter Shor is brilliant, and his algorithms are marvelous works. If no one implements them, for whatever reasons, they won’t be any less marvelous, and he won’t be any less brilliant.

And for that matter, Hill and Viamonthes may turn out to be wrong, too. Or they may inspire someone to a tweak that makes Shor’s algorithm work (or work better).

The present spectator sport is how science works. It’s what makes it exciting.

Bush’s Law — Less Safe, Less Free

bushs-law.jpg
less-safe-less-free.jpg
I’d like to review two recent books on the war on terror: “Bush’s Law: The Remaking of American Justice” by by Eric Lichtblau, and “Less Safe, Less Free: Why America Is Losing the War on Terror” by David Cole and Jules Lobel. Both are well written assaults on the way in which the Bush administration is conducting itself, although each takes a tact aligned with the author’s background and history. Lichtblau is a reporter, currently for the New York Times, and Cole and Lobel are law professors.

Bush’s Law is an extended view into some of the major stories that Lichtblau has covered. Included are the NSA’s warrant-less wiretapping, the SWIFT following of the money, and the Comey/Ashcroft hospital story. Even as someone who follows these stories fairly closely, I still learned quite a bit-some new, some not previously reported, and all better organized and more readable than in the newspaper. The theme that emerges from Bush’s Law is one of secrecy, and the conflict which a free society faces when repeatedly begged to `trust us’ by an administration which seems to not understand how its actions undermine trust.

The undermining of trust is also a major theme of Less Safe, Less Free. Before getting into the meat of the book, let me say that this is law professor writing at its best. It’s clear and compelling, and the notes are at the end. They lay out a strong case that the Bush administration’s concept of how to engage with the world is is at its core, preventative, rather than reactive. In theory, this seems like a great plan. In practice Cole and Lobel show how it inevitably undermines the concepts of justice on which our society is founded, as well as our reputation with the rest of the world. That is, it is not merely a practical failure, it was inevitably going to be a practical failure. Predictions are hard, especially about the future. Reasonable people may disagree on the reasonableness of a preventative action. The difficulty of reaching proof “beyond a reasonable doubt” about what would have happened undermines the legitimacy of claims about the future.

The essence of their argument is that prevention, be it preventative war, such as in Iraq, or preventative law enforcement, such as with the justice, always requires the showing of evidence. You can’t simply detain someone because they might in the future commit a crime. In a court, no single body acts as judge, jury and executioner. Each party gets their day in court, with an opportunity to examine the evidence against them. These things are impossible in the preventative paradigm. Not only are sources and methods secret (sometimes with good reason), but the evidence is often lacking. In the case of war, the court is that of public opinion in many places. They also show a plethora of historical cases where preventative war went horribly wrong, and relate preventative war to a set of regimes with which no reasonable person wants to be associated.

The core reason which we demand that justice be reactive, or, at its fastest, at the instant of a crime, is that we rightfully fear the powers we invest in our government. It is a mighty and fearsome machine which can crush anything in its path. When it is allowed to do so, we are all less safe, and less free.

Two asides: I paid for both books, and I love the endnote styling of page number, excerpt, note used in Bush’s Law.

Quantum Uncertainty

Technology Review has a pair of articles on D-Wave‘s adiabatic quantum computer. Quantum pioneer Seth Lloyd writes in “Riding D-Wave” about quantum computing in general, adiabatic quantum computing, and D-Wave’s efforts to show that they’ve actually built a quantum computer.

Linked to that is Scott Aaronson’s article, “Desultory D-Wave,” in which Lloyd’s nail-biting is made a bit more plain. I hate giving away the punch line, but here’s what Aaronson sums up with:

Let me be clear: I think that quantum computers are possible in principle, and that D-Wave’s approach might even get us there. I’ve also met people from D‑Wave; I don’t think they’re frauds. But the human capacity for self-deception being what it is, scientists train themselves to look for red flags–and D-Wave is pretty much a red-flag factory.

Beyond that, there’s a new paper that shows problems not in just one implementation of quantum computing, but about its very theoretical core. In “Operator Imprecision and Scaling of Shor’s Algorithm,” authors C. Ray Hill and George F. Viamontes claim that Shor’s Algorithm doesn’t work at an interesting scale.

The reason is that errors in the quantum fourier transforms accumulate faster than quantum error correcting codes can get rid of them, particularly when factoring the sort of numbers that a sane person might use for a public key. Hill and Viamontes seem to think that it is not possible to factor a key much more than 256 bits in length. Most importantly of all, the errors accumulate linearly with the number of quantum operations and the number of operations increases polynomially with the size of the integer. My peeks at the error rate graph lead me to guess that a hard limit is reached before you get to a 512-bit number, which is no longer considered interesting using conventional sieve methods.

Here is their abstract:

Shor’s algorithm (SA) is a quantum algorithm for factoring integers. Since SA has polynomial complexity while the best classical factoring algorithms are sub-exponential, SA is cited as evidence that quantum computers are more powerful than classical computers. SA is critically dependent on the Quantum Fourier Transform (QFT) and it is known that the QFT is sensitive to errors in the quantum state input to it. In this paper, we show that the polynomial scaling of SA is destroyed by input errors to the QFT part of the algorithm. We also show that Quantum Error Correcting Codes (QECC) are not capable of suppressing errors due to operator imprecision and that propagation of operator precision errors is sufficient to severely degrade the effectiveness of SA. Additionally we show that operator imprecision in the error correction circuit for the Calderbank-Shor-Steane QECC is mathematically equivalent to decoherence on every physical qubit in a register. We conclude that, because of the effect of operator precision errors, it is likely that physically realizable quantum computers will be capable of factoring integers no more efficiently than classical computers.

Hill and Viamontes also claim that this brings up a serious question about quantum computing in general. Take a deep
breath and read this:

It is natural to ask whether these results have wider implications about the power of quantum computers relative to classical computers. While the results presented in this paper do not answer this question definitively, it is important to note the singular stature of Shor’s algorithm as the only quantum algorithm that appears to efficiently solve a classically intractable problem. The
fact that Shor’s algorithm is not more efficient than classical algorithms removes the only strong evidence for the superior computational power of quantum computers relative to classical
computers.

Wow. They have by no means the last word on this, but this means that quantum computing is going to get much more interesting as a spectator sport. And perhaps this fall’s Post-Quantum Cryptography workshop will be a little less interesting.

The messenger is the message

In a blog post entitled “Lending Tree A Little Late In Cutting Off Network Access?“, I read that in the recent Lending Tree breach:

several former employees may have helped a handful of mortgage lenders gain access to Lending Tree’s customer information by sharing confidential passwords with the lenders.

Later, the author describes “an obvious chink in Lending Tree’s information security armor”, (reprinting a U.S. News quotation from Brian Cleary):

These are former employees—how can those user accounts to critical customer data still be active? Those should be shut down. So, their access to all of the information and resources should be revoked on the day of their termination.

USNews.com
Finally, he observes that

If you’re going to rely primarily on human beings to implement the policies, then you’d better make sure that those human beings are either themselves subject to checks and reviews to make certain that they’re following the policies.

All of this is nothing new to EC readers. What surprised me, and what I think is noteworthy here, is that the guy writing this is not some CISSP, CISA, or even CISO. He’s the voice behind the Bank Lawyer’s Blog, an attorney with banking and other corporate clients.
Not to read too much into this, but when the legal profession starts commenting knowledgeably about access termination policies, there’s something interesting afoot.

Who Watches the Watchlists?

The idea of “watchlists” has proliferated as part of the War on Terror. There are now more than 63 of them:

As part of its regular “risk management” service, which provides screening, tracing, and identity and background checks on potential clients or trading partners, MicroBilt will now offer a “watch list” service that checks these individuals against 63 different lists from 35 sources, including OFAC, the FBI, and Interpol, Bradley says. (“Companies May Be Held Liable for Deals With Terrorists, ID Thieves“, DarkReading)

I say more than 63 because some unknown number are secret. The poor souls who find themselves on these lists have, in essence, no recourse. Convincing 35 or more agencies that their presumption of your guilt is incorrect might, in theory, be possible. In reality, the agency has no reason to do anything but drag its feet: there are no penalties to them for declaring you guilty. In contrast, a failure to put your name on the list risks them not having prevented you from your future thoughtcrime.

But there’s hope. And it’s not in MicroBilt’s stock price (MicroBilt is a subsidiary of First Advantage). Rather, it’s in the courage of a judge, who ruled that any American who has been routinely detained because they are on a watch list knows that they are on a list, and thus the government’s ‘State Secrets’ privilege isn’t applicable:

since the government admits it has stopped the six men and two women more than 35 times, federal Magistrate Judge Sidney Schenkier of the United States Northern Illinois District Court dismissed that argument. Instead he found that the government “failed to establish that, under all the circumstances of this case, disclosure of that information would create a reasonable danger of jeopardizing national security.” (“ Court: Government Must Reveal Watch-List Status to Constantly Detained Americans,” Wired’s excellent 27B-6 Mk IIa blog)

Security Metric?

Ross Anderson has made PDF versions of several chapters of his Security Engineering (second edition) available on-line. The entire first edition has been available for some time.
I am sure this second edition will be outstanding. I would rank the first edition as one of the top three technical books I’ve read. It would likely be number one. I have high expectations for the second edition, stemming in large part from the author’s academic discipline.
How many security titles have a 104 page bibliography?

Good problems to have

You don’t have much credibility looking for a publisher for a book on rum when you’re sailing in the Caribbean drinking the best rums you can find in the name of research. Most people just didn’t take me seriously that there was even a need for a book on rum. It took quite a while to get things rolling.

See the Ministry of Rum FAQ.

University of Miami: Good for the body, bad for the soul?

The University of Miami has chosen to notify 41,000 out of 2.1 million patients whose personal information was exposed when thieves stole backup tapes.

The other 2.1 million people, apparently, should be reassured, that their personal medical data was stolen, but the University feels it would be hard to read, and well, there’s no financial identity theft risk associated with it. If you believe the sorts of people who notify 1.9% of the victims of a breach. Sorry, ChoicePoint. Unfair comparison. You notified about 18% of the victims*, nearly ten-fold as many.

There’s some analysis of how hard it would be to read the tapes. I’m skeptical: why does someone steal tapes from an Iron Mountain van if not to read them?

The Breach Blog feels differently. In “University of Miami reports stolen tapes affecting patients,” he digs into the likelihood of the data being accessed.

Now, the University claims that the tapes are in a “complex and proprietary format,” which seems to be “Tivoli Storage Management” from IBM. Now, Tivoli storage manager has encryption capabilities (page 3 of this PDF.) I’m curious why that wasn’t in use.

Also, looking around, I found this quote at an IBM partner site:

Much is made of the inbred security of the TSM system since the backed up data is so closely linked with the TSM database. While, to the layman this is true, and it is almost impossible to reconstruct TSM data without the database, it is possible in the right scenario, with the right skills at your disposal.

Until I hear more, I’m skeptical of the University’s claims. I don’t believe, and I have not believed for a long time, that breach notices are about identity theft. They’re about the performance of a promise to protect information.

(*Footnote: 18% being 30/160, approximate numbers for the ChoicePoint incident.)