Emergent Chaos

Let's not ask the experts?

Can Sips at Home Prevent Binges? is a fascinating article in the New York Times. It turns out there's very solid evidence about this:

“The best evidence shows that teaching kids to drink responsibly is better than shutting them off entirely from it,” he told me. “You want to introduce your kids to it, and get across the point that that this is to be enjoyed but not abused.”

...
What is the evidence? In 1983, Dr. George E. Vaillant, a professor of psychiatry at Harvard University, published “The Natural History of Alcoholism,” a landmark work that drew on a 40-year survey of hundreds of men in Boston and Cambridge.

Ironically, the Times decided to ask their readers: "Do you think teenagers drinking wine with their parents at home encourages reckless drinking or more responsible habits with alcohol later in life?" See the sidebar. Without any disrespect to people reading the Times, why would we care what they think about this? We have evidence of what really happens. Why not ask "Why do you think we can't fix a broken law?" or "Would you vote for a candidate who promised to fix these laws?"

Relatedly, Adam Barr wrote:

I saw an article today about how the Smart ForTwo (that tiny car you see around) had earned top marks in safety tests conducted by the Insurance Institute for Highway Safety. Despite this, the Institute decided to disqualify the car from potentially earning its "Top Safety Pick" designation because it is just too dang small. "All things being equal in safety, bigger and heavier is always better," says the president of the Institute. ("Things that Everybody Knows.")

Experts are experts because they have data and the tools to analyze them. That's why we listen to them. When did we become so resistant to science?

A question of ethics

Various estimates have been made regarding the quantity of personal identifying information which has been exposed by various mechanisms. Obviously, though, we only know about what we can see, so seeing more would make such estimates better. One way to see more would be to look in more places, for example on peer-to-peer file sharing networks. So here's the question: would it be ethical (and if so, under what conditions) to deliberately seek out files containing PII as made available via P2P networks, in order to better understand the extent to which such information is exposed, and how? I have an opinion on this question, but I'm very interested in what others think.

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.

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.

Quantum Cryptography Broken and Fixed

Researchers at Linköping University in Sweden have found flaws in quantum cryptography. They also supply a fix. The announcement is here; a FAQ is here; full paper is at the IEEE here (but requires an IEEE membership).

The announcement says:

Jan-Åke Larsson, associate professor of applied mathematics at Linköping University, working with his student Jörgen Cederlöf, has shown that not even quantum cryptography is 100-percent secure. There is a theoretical possibility that an unauthorized person can extract the key without being discovered, by simultaneously manipulating both the quantum-mechanical and the regular communication needed in quantum cryptography.

Interestingly, the fix is to add some random bits into the channel. My understanding (I haven't read the paper, just the announcement and the FAQ) is that this effectively adds a nonce to the protocol. I am amused that even an allegedly pure-physics security system needs a software patch.

This brings up an interesting question, though -- if, with all its hype, quantum cryptography is not 100% secure, how secure is it? Is it 99.999999999999% secure? And why wouldn't you just use 256-bit conventional crypto on a pair of IPsec routers you bought at Fry's instead?

Science in Action

The New Scientist reports in, "Have peacock tails lost their sexual allure?"

A controversial study has found no evidence for the traditional view – practically enshrined in evolutionary lore – that peahens choose their partners depending on the quality of the peacocks' tails.

Obviously, traditionalists have many things to say about the quality of the study. Because, of course, everyone knows it's true.

Thank you, Usenix!

I'm delighted to report that USENIX, probably the most important technical society at which I publish (and on whose board I serve), has taken a long-overdue lead toward openly disseminating scientific research. Effective immediately, all USENIX proceedings and papers will be freely available on the USENIX web site as soon as they are published. (Previously, most of the organization's proceedings required a member login for access for the first year after their publication.)

For years, many authors have made their papers available on their own web sites, but the practice is haphazard, non-archivial, and, remarkably, actively discouraged by the restrictive copyright policies of many journals and conferences. So USENIX's step is important both substantively and symbolically. It reinforces why scientific papers are published in the first place: not as a proprietary revenue source, but to advance the state of the art for the benefit of society as a whole.

From Matt Blaze, "USENIX to make all conference proceedings freely available."

Quantum Progress

What is it about the word "quantum" that sucks the brains out of otherwise reasonable people? There has to be some sort of Heisenberg-Schödinger Credulity Principle that makes all the ideons in their brains go spin-up at the same time, and I'm quite sure that the Many Worlds Interpretation of it has the most merit. (In case you're a QM n00b, the ideon is the quantum unit of belief.) Fortunately, there seems to be some sanity coming to reporting about quantum computing.

Just about every quantum computing article has a part in it that notes that there are quantum algorithms to break public crypto. The articles breathlessly explain that this means that SSL will be broken and the entire financial world will be in ruins, followed by the collapse of civilization as we know it. Otherwise sensible people focus on this because there's very little to sink your teeth into in quantum computing otherwise. Even certified experts know that they don't know what they don't know.

Scott Aaronson has a good article in Scientific American called "The Limits of Quantum Computers" (only the preview is free, sorry) that gives a good description of what quantum computers can't do. I'm pleased to see this. SciAm has been a HSCP-induced quantum cheerleader over the last few years.

I have been doing some research on the claims of quantum computing. I decided to pick the specific factoring ability of quantum computers, and produce some actual numbers about how we might expect quantum computing to develop. In other words, I'm going to be a party pooper.

The crypto-obviating algorithms in question are Shor's algorithm for factoring and an algorithm he developed for discrete logs. I was surprised to learn that Shor's algorithm requires 72k³ quantum gates to be able to factor a number k bits long. Cubed is a somewhat high power. So I decided to look at a 4096-bit RSA key, which is the largest that most current software supports — the crypto experts all say that if you want something stronger, you should shift to elliptic curve, and the US government is pushing this, too, with their "Suite B" algorithms.

To factor a 4096-bit number, you need 72*4096³ or 4,947,802,324,992 quantum gates. Lets just round that up to an even 5 trillion. Five trillion is a big number. We're only now getting to the point that we can put about that many normal bits on a disk drive. The first thing this tells me is that we aren't going to wake up one day and find out that someone's put that many q-gates on something you can buy from Fry's from a white-box Taiwanese special.

A complication in my calculations is the relationship between quantum gates and quantum bits. For small numbers of qubits, you get about 200 qugates per qubit. But qubits are rum beasts. There are several major technologies that people are trying to tease qubits out of. There's the adiabatic techlogies that D-Wave is trying. There are photon dots, and who knows how many semiconductor-based methods.

It isn't clear that any of these have any legs. Read Scott Aaronson's harumphing at D-Wave, more pointed yet sympathetic faint praise and these educated doubts on photonics. Interestingly, Aaronson says that adiabatic quantum computers like D-Wave need k¹¹ gates rather than k³ gates, which pretty much knocks them out of viability at all, if that's so.

But let's just assume that they all work as advertised, today. My next observation is that probably looking at billions of q-bits to be able to get trillions of q-gates. My questions to people who know about the relationship between quantum gates and quantum bits yielded that the real experts don't have a good answer, but that 200:1 ratio is more likely to go down than up. Intel's two-billion transistor "Tukwila" chip comes out this year. Five trillion is a big number. We are as likely to need 25 billion qbits to factor that number as any other good guess. Wow.

The factoring that has been done on today's quantum computers is of a four-bit number, 15. If you pay attention to quantum computing articles, you'll note they always factor 15. There's a reason for this. It's of the form (2ⁿ-1) * ( 2ⁿ+1). In binary, 2ⁿ-1 is a string of all 1 bits. A number that is 2ⁿ+1 is a 1 bit followed by a string of 0s, and then a 1 again. These numbers are a special form that is easy to factor, and in the real world not going to occur in a public key.

This is not a criticism, it's an observation. You have to walk before you can run, and you have to factor special forms before you can factor the general case. Having observed that, we'll just ignore it and assume we can factor any four-bit number today.

Let's presume that quantum computers advance in some exponential curve that resembles Moore's Law. That is to say that there is going to be a doubling of quantum gates periodically, and we'll call that period a "generation." Moore's specific observation about transistors had a generation every eighteen months.

The difference between factoring four bits and factoring 4096 bits is 30 generations. In other words, 72*4³ * 2³⁰ = 72*4096³. If we look at a generation of eighteen months, then quantum computers will be able to factor a 4096-bit number in 45 years, or on the Ides of March, 2053.

This means to me that my copy of PGP is still going to be safe to use for a while yet. Maybe I oughta get rid of the key I've been using for the last few years, but I knew that. I'm not stupid, merely lazy.

I went over to a site that will tell you how long a key you need to use, http://www.keylength.com/. Keylength.com uses estimates made by serious cryptographers for the life of keys. They make some reasonable assumptions and perhaps one slightly-unreasonable assumption: that Moore's Law will continue indefinitely. If we check there for how long a 4096-bit key will be good for, the conservative estimate is (drum roll, please) — the year 2060.

I'm still struck by how close those dates are. It suggests to me that if quantum computers continue at a rate that semiconductors do, they'll do little more than continue the pace of technological advancement we've seen for the past handful of decades. That's no mean feat — in 2053, I doubt we're going to see Intel trumpeting its 45 picometer process (which is what we should see after 30 generations).

I spoke to one of my cryptographer friends and outlined this argument to him. He said that he thinks that the pace of advancement will pick up and be faster than a generation every eighteen months. Sure. I understand that, myself. The pace of advancement in storage has been a generation every year, and in flash memory it's closer to every nine months. It's perfectly conceivable that quantum computing will see horrible progress for the next decade and then whoosh off with a generation ever six months. That would compress my 45 years into 25, which is a huge improvement but still no reason to go begging ECRYPT for more conferences.

On the other hand, it's just as conceivable that quantum computing will end up on the Island of Misfit Technologies, along with flying cars, personal jetpacks, Moon colonies, artificial intelligence, and identity management.

But I also talked to a bigwig in Quantum Information Theory (that's quantum computing and more) and gave him a sketch of my argument. I heard him speak about Quantum Information and he gave the usual Oooooo Scary Quantum Computers Are Going to Factor Numbers Which Will Cause The Collapse of All Financial Markets And Then We Will All DIEEEEE — So That's Why We Need More Research Money boosterism.

He wouldn't let me attribute anything to him, which I understand completely. We live in a world in which partisanship is necessary and if he were seen putting down the pompoms, he'd be fired. Telling middle-aged technocrats that the math says their grandkids are going to see quantum computers shortly before they retire will cause the research money dry up, and if that happens then — well, the world won't end. And then where would we be?

Nonetheless, he said to me sotto voce, "There's nothing wrong with your math."

Photo is a detail from "Shop Full" by garryw16.

Wanted

Via Michael Froomkin.

Guinness is Good For You, but don't tell anyone

A pint of the black stuff a day may work as well as an aspirin to prevent heart clots that raise the risk of heart attacks.

Drinking lager does not yield the same benefits, experts from University of Wisconsin told a conference in the US.

...

The researchers told a meeting of the American Heart Association in Orlando, Florida, that the most benefit they saw was from 24 fluid ounces of Guinness - just over a pint - taken at mealtimes.

They believe that "antioxidant compounds" in the Guinness, similar to those found in certain fruits and vegetables, are responsible for the health benefits because they slow down the deposit of harmful cholesterol on the artery walls.

Even though it's true, companies are scared of making health claims for booze. "Draft legislation could outlaw any health claims in adverts for alcohol in Europe, [a spokeswoman for Brewing Research International] said."

It's sad when the ability to make true statements is suppressed because 'authorities' worry that people are too dumb to listen to a bunch of statements and make up their own minds.

All quotes from the BBC, "Guinness good for you - official"

"There's supposed to be a Mars-shattering Ka-boom!"

Here at Emergent Chaos, we're big fans of large objects hitting other large objects at high speed. Which is why it's important to tell you that 2007-WD5 is a 50 meter asteroid that's set to pass within 48,000 kilometers of Mars next month.

"We estimate such impacts occur on Mars every thousand years or so," said Steve Chesley, a scientist at JPL. "If 2007 WD5 were to thump Mars on Jan. 30, we calculate it would hit at about 30,000 miles per hour and might create a crater more than half-a-mile wide." The Mars Rover Opportunity is exploring a crater approximately this size right now. (JPL press release.)

More details about the orbit at the JPL small-body datatbase. Story via VOA news.

Bonobos!

Check out this amazing video from TED.

Laboratories of Security?

There's a story in USA Today, "Most fake bombs missed by screeners." It describes how screeners at LAX find only 25% of bombs, at ORD, they find 40%, and at SFO, 80%:

At Chicago O'Hare International Airport, screeners missed about 60% of hidden bomb materials that were packed in everyday carry-ons — including toiletry kits, briefcases and CD players. San Francisco International Airport screeners, who work for a private company instead of the TSA, missed about 20% of the bombs, the report shows. The TSA ran about 70 tests at Los Angeles, 75 at Chicago and 145 at San Francisco.

I could go on at length about how bad air travel has gotten, and how security theatre is crushing the travel and tourism industries in the US. Rather I'd like to focus on the emergent chaos aspects of this story: the reality that even TSA bureaucracy can't impose standards on airports, and why that would be a good thing, if they could accept it.

Before I do, I want to comment that missing 75% of the bombs is probably ok. There are very few airliners bombed in the US. I think it's less than 10 in history. So the issue is not really false negatives, where the screener misses a real fake bomb, but false positives, where the screener shuts down either someone's day or the airport. Given that every single bomb smuggled past security last year at US airports was fake, they are far more likely than real bombs.

Now, there's an opportunity for dramatic improvement in the way we run airport security. "Just run them all like they run SFO!" Orin Kerr makes this point, "I would think the real story is the dramatic gap between the performance of TSA employees and private sector employees."

More importantly, what comes out of this study for me is the emergent chaos of running a large mission like airport security, and the value of that variation for learning.

If all airports were run exactly the same, we'd have missed this opportunity for learning.

So ask yourself, what do I standardize on too much? Where is there too much structure, inhibiting learning? How can we harness chaos, and what emerges? (I talk in more deatil about a very similar point in the latest post in my threat modeling series on the SDL blog, "Making Threat Modeling Work Better.")

Photo: Frisk, by Tim Whyers. (Machine by Tim Hunkin, we've mentioned it previously.)

Links of the day

http://plato.stanford.edu/entries/economics/
http://faculty.fuqua.duke.edu/~rnau/choice/whoswho.htm

(Also useful as a reading list for a possible upcoming cage match between Hutton and Bejtlich ;^))

Typical British overstatement

I saw a BBC headline, "Huge payout in US stuttering case", and figured that somebody who stutters must have been harassed at work or something, and got a settlement of $5 mil. WRONG.

What happened is this:

Six US citizens who, as children, were used in an experiment that tried to induce stuttering have been awarded nearly $1m (£500,000) in compensation.

In 1939, the plaintiffs - all orphans in state care - were tormented for six months by Iowa University researchers.

The study was testing the theory that children develop speech impediments because of psychological pressure.

The truth behind this atrocity came out in 2001. Again, the Beeb:

The 1939 experiment was dubbed The Monster Study because of the researchers' methods.

Over a period of six months, Dr Wendell Johnson, a pioneer in speech pathology, tested his theory on 22 children from the Iowa Soldiers' Orphans' Home.

Some were subjected to prolonged harassment, while the remainder were used as a control group.

None of the children became stutterers but some became self-conscious and reluctant to speak, according to the study.

In 2001, a Californian newspaper revealed details of the secretive study, basing its story on the testimony of a former research assistant.

Iowa's Attorney General, not to mention the people that govern its University system, should hang their heads in shame. A million bucks for psychologically abusing orphans for six months is a pittance.

Doctors want more study on overuse of books

(Adds psychiatrist interview, industry comment, paragraphs 4, 7-17)

CHICAGO, June 27 (EmergentChaos)- The American Medical Association called for more research into the public health risks of books and reading on Wednesday but stopped short of declaring them addictive.

The AMA, which recommended a review of the current publishing system, also said it would leave it up to the American Psychiatric Association and other experts to decide whether reading addiction should be designated a mental illness.

"While more study is needed on the addictive potential of books, the AMA remains concerned about the behavioral, health and societal effects of book and library overuse," said AMA president Dr. Ronald Davis. Davis said research has linked exposure to media violence with increased aggressive behavior.

The AMA's debate over reading addiction at the group's annual meeting touched a nerve among doctors, who are not sure what to tell patients and worried parents.

"To the extent that a book is controlling someone's behaviors and taking over their daily life, then you are talking about a compulsive use, whether you categorize it in a psychiatric manual or not," Davis told reporters at a news briefing.

Dr. Timothy Fong, a psychiatrist at the University of California at Los Angeles who specializes in addiction, said books could be a problem for some.

"Anything in the world can be addictive if you have that biological vulnerability to develop an addiction," he said in a telephone interview.

"This is a brain disease for a very small percentage of kids, but not all kids can become addicted to books."

Fong said there needs to be more empirical research into the effects of books, especially on children.

"Otherwise, we are just spouting out myths and stereotypes," he said.

SECOND OPINION

Addiction experts strongly opposed a push earlier this week at the AMA's annual meeting to declare video game addiction a mental illness and recommend its inclusion in the American Psychiatric Association's Diagnostic and Statistical Manual of Mental Disorders.

Fong said parents should be involved in what their children are playing, because different children experience games differently.

He compared two adolescents he recently saw, one with a games problem. "His grades are suffering. He is trying to hide his game play from his parents," Fong said.

The other boy plays sports as well as reads and has "a wonderful home life." "He has other interests," Fong said. "That is someone who does not have an addiction."

Ray Bradbury, president of the National Publishers Forum, which represents the $30 billion global publishing industry, said the group understands parents' concerns.

"Our industry encourages consumers to enjoy books just as they do any other leisure activity: responsibly and in moderation as part of a well-rounded, well-adjusted lifestyle," he said. "As a science fiction author, I predicted medicalizing childish behaviors decades ago, so it's not like this is surprise to us."

Update (27 June): During the transcription of this article, a number of errors were inadvertently introduced. Among them, the words "video game" was accidentally rendered as "book." Also, the second part of Mr. Bradbury's quote does not appear in the original article, nor was it Mr. Bradbury who made the comment. Emergent Chaos regrets the error.

She's Such A Geek

Longtime geek author Annalee Newitz and Charlie Anders, published She's Such A Geek last year. I've been meaning to blog about this for a while It's a collection of over 20 essays by women geeks. These essays cover the trials, tribulations and joys of being a female geek. At times entertaining and other times depressing, the book highlights both how far feminism has gotten over the last hundred years and how much more it has to accomplish. I can't recommend the book or the associated blog enough.

Portuguese Got to Australia in 1522

Portuguese seafarer Christopher de Mendonca led a fleet of four ships into Botany Bay in 1522. No one noticed before because the map was oriented wrong when it was copied. This is a nice article from news.com.au.