Emergent Chaos

Adam on "Silver Bullet Security" Podcast

The 26th episode of The Silver Bullet Security Podcast features Adam Shostack, a security expert on Microsoft’s Secure Development Lifecycle team who has also worked for Zero Knowledge and Reflective. Gary and Adam discuss how Adam got started in computer security, how art/literature informs Adam’s current work, and the main ideas behind Adam’s new book The New School of Information Security. They go on to chat about Adam’s aversion to the term “best practices,” the role IEEE Security & Privacy magazine plays in bringing the science of security to a practical level, and whether the biggest problem of the CardSystems breach was the following the letter, rather than the spirit, of PCI. Also on the agenda, duck-billed platypuses, Kandinski, and books by Pynchon.

Show 026 - An Interview with Adam Shostack.

The one thing I'd like to add is that we mentioned Frank Abagnale's Catch Me If You Can.

It was a fun interview.

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.

Edward Lorenz, 1917-2008

Edward Lorenz, most famous for research concerning the sensitivity of high-level outcomes to seemingly insubstantial variations in initial conditions (the so-called "butterfly effect"), died April 16 in Cambridge, Massachusetts.

Much more information concerning Lorenz's life and work is available via Wikipedia.

Generativity, Emergent Chaos and Adam Thierer

Jonathan Zittrain, a professor at Oxford, has a new book, "The Future of The Internet." He's adapted some of the ideas into a long and worthwhile essay, "Protecting the Internet Without Wrecking It."

In that essay, he uses the term "generativity" to refer to a system which has what I would call 'emergent chaos.' A generative system is one which is open enough that people do strange things on it, and new stuff emerges. There's no need to get permission. In The New School, we talk about the difference between the internet, where anyone can run anything, and the old phone network, where only Ma Bell had any way to innovate. And never did.

In commenting on these ideas, Adam Thierer says some things I want to respond to:

I see no reason why we can’t have the best of both worlds–a world full of plenty of tethered appliances, but also plenty of generativity and openness. In a follow-up essay, I pointed out how Apple’s products create a particular problem for Zittrain’s thesis because even though they are “sterile and tethered,” there is no doubt that the company’s approach has produced some wonderful results.

...

And what’s wrong with this? Answer: Nothing! People are getting the choices and configurations they want. Older generations are simply not comfortable with the “general purpose” devices that tinker-happy gadgeteers like Zittrain and me prefer.

(From "another problem for the Zittrain thesis — old people!")

So I'm all for choice in who gets what. At the same time, I think that Thierer makes the mistake of thinking that generativity happens in a vacuum. I don't think it does. I think that the more generative devices you have, the more chaos (both good and bad) emerges. If only a few hundred people have Chumbys, then no one is going to write the alarm clock my buddy Nathan wants.

On the other hand, if there are a million Chumbys then someone might.

I think anyone writing for a blog entitled "The Technology Liberation Front" would get this, but let me lay out it. If I'm thinking of creating a widget to connect an ipod to a stereo, then I have to pay for my R&D out of the sale price of each device. If I'm spend a million bucks on R&D, then if I sell a million units, I can add a buck to the price of each. If I sell 10, then I'm going to lose money.

Entrepreneurs know this. They learn to prefer larger markets. They gravitate to larger markets. And thus the larger markets develop an advantage, which is that people want to participate, there's a talent pool available, there's a greater opportunity to partner, more investors willing to invest, etc. It's a virtuous circle. You can buy a wider variety of parts to customize a Scion or a Mini than you can with a Ferrari. There just aren't enough Ferarris to support a broad ecosystem of innovation. (There may be a network of engineers who wouldn't bother touching a lower end car.)

And so each "tethered" device may reduce generativity by reducing the chaotic froth which exists in the generative world. I'm not saying that such devices have no innovation. I have (and enjoy) an iphone. I'd love to be able to SMS people URLs or contacts. And maybe when we get the SDK, and the iPhone becomes generative, I'll be able to.

Until then, generativity has existed in active conflict tension with the tethering. I think that generative and tethered systems can co-exist. But it's not the "best of both worlds."

Obama vs. McDonalds

As he was winning contests in Iowa and South Carolina, Senator Barack Obama raised $32 million in January for his presidential bid, tapping 170,000 new contributors to rake in nearly double the highest previous one-month total for any candidate in this election cycle.

The New York TImes, "Enlisting New Donors, Obama Reaped $32 Million in January"

Which is to say that, in a month, Obama raised half a day's revenue for McDonalds, who in the last quarter of 2007, took in 5,753.6 million dollars.

It's too bad that (Presidential candidate) John McCain is opposed to Americans spending their money on something, like the Presidency, which really matters.

Now last time I mentioned this, a lot of people asked about public funding for elections. One of the things which I find interesting about this election cycle is that two candidates, Obama and Huckabee, essentially came out of nowhere. A system of public funding has to be restricted to serious candidates. We wouldn't want Mike Huckabee to be treated the same as Vermin Supreme, would we?

How can a public funding system allow for "out of the blue" candidates who challenge their party's accepted wisdom about who the nominee "should" be?

The Emergent Chaos of the US Presidential Campaign

This New York Times really is interesting. It's all about how candidates are losing control of their campaigns, and they're in a new relationship with emergent phenomenon on the internet.

Now, as we come to the end of a tumultuous political year, it seems clear that the candidates and their advisers absorbed the wrong lessons from Dean’s moment, or at least they failed to grasp an essential truth of it, which is that these things can’t really be orchestrated. Dean’s campaign didn’t explode online because he somehow figured out a way to channel online politics; he managed this feat because his campaign, almost by accident, became channeled by people he had never met.

... Meanwhile, those candidates who have amassed roomfuls of well-paid online experts have frequently found themselves buffeted or embarrassed (or sometimes both at once) by mysterious forces outside their grasp. ("The Web Users' Campaign," The New York Times.)