Area 51

Complexity Theory Conspiracy Theories

Graham Steel is a member of Team Prosecco at INRIA Paris-Roquencourt in France. He along with Romain Bardou of the related SECSI team at INRIA, and Riccardo Focardi, Yusuke Kawamoto, Lorenzo Simionato, and Joe-Kai Tsay in other countries, have written a paper to appear at CRYPTO 2012 that shows how to break RSA tokens in record time. The INRIA team names combine to say that dry white wine is sexy, which makes us think of spy movies, which often involve conspiracies.

Today Ken and I want to talk about possible conspiracy theories that involve computational complexity.

We learned of this through my Georgia Tech colleague Chris Peikert being quoted in the New York Times article on the story. The RSA secure token system is is a hardware device that is widely used by industry and governments. They have at least dented the system if not destroyed it. Of course following research crypto etiquette they have published their results, rather than keep them secret. But what if they had decided to keep them secret? What if we did not know that the RSA token system is breakable? Indeed.

The 2012 film “Travelling Salesman” has a similar premise. Four mathematicians have found a polynomial-time algorithm for TSP, so that not only all other NP-complete problems but also Factoring and related crypto problems have polynomial-time algorithms. They wrestle with the government officials’ desire to keep their discoveries secret. Although the film has been out for two weeks, its Wikipedia page currently lists its only critical reaction as coming from … us. And neither of us has seen the movie yet. What do you do when life becomes a house of mirrors?

All this sets us thinking hard about possible conspiracy theories. Were the sexy wine people the first to discover the RSA token flaw? Did others know about it for years and not announce their results? This detailed blog post by Matthew Green shows trouble brewing for years. But then why involve Chris, who isn’t even cited in the paper or any other coverage we’ve seen? Is all this a warning for us to go underground, to be seen only as “Pip”? One can get a pretty neat conspiracy theory started here. Hence this discussion.

Conspiracy Theory Theory

Conspiracy theories come in “historical” and “futuristic” flavors. Historical ones try to explain some real world events as having been caused by a covert group or group-within-a-group, which by definition is unknown to most of us. Futuristic ones postulate something that is currently unknown, and the group concerned may even be known.

Our friends at Wikipedia have a list of prominent theories here. It is interesting to note that Katherine Young states

“…(t)he fact remains, however, that not all conspiracies are imagined by paranoids.”

And we add, not all conspiracy theories are wrong either. It is incontestably true that a US President was assassinated by conspiracy in the ’60s: Lincoln. How might we possibly tell which are which?

One of the most fun recent conspiracy theories is based on the upcoming London Olympic Games. Their logo is:

Go here for an amusing, we think, discussion of how school children actually designed the logo via tangrams. This is a nice example of a fun theory.

Well there is also a non-fun theory: Iran threatened to boycott the Games based on the rumor that the logo really spells “Zion”—as if the Illuminati were behind it. The main supporting argument is that the little central diamond cannot be part of “2012,” but goes neatly as the dot for the ‘i’ in “Zion.”

However the tangram aesthetic has something to say here. How many of you like us have doodled during lectures or meetings, the kind of doodle where you make a 2-coloring where regions touch at points? The diamond similarly holds the other parts of the London 2012 logo together.

With historical conspiracy theories the known event E is presumed unlikely without the conspiracy as explanation—but usually the conspiracy itself should be presumed unlikely. When an alternative explanation is natural enough to have higher prior likelihood, such as we claim for the logo’s diamond, that’s concrete evidence against the theory. In the futuristic case the relevant “prior probabilities” may be harder to judge, but current expertise may enable one to gauge them.

Ten Theory Theories

Let’s turn now to computer and complexity based conspiracy theories. We are kidding here—let us repeat, we are just having fun. We do not really believe any of these on our “Top Ten” list—or do we?

Quantum Computers Already Exist. Notwithstanding—cool to use that word—our recent many columns on quantum computers, some believe that they already exist. Certain agencies here and elsewhere might be running one right now—how could we know?

Now to test our framework, is it true that those skeptical of quantum computing are the ones who assign the lowest “prior” to this unknown postulate? Or does the allegedly conspiratorial nature of the skepticism correlate positively with it? On the other hand, does a technological advance like this one with ion traps enhance the postulate?

Factoring Really Is Easy. This is similar to the last, but now they can factor in polynomial time on a laptop, rather than need a quantum computer. Ken and I think this one has a much higher prior, almost on the order of “Breaking Engima Really Is Easy” in 1939.

John von Neumann’s Proof. Recall that Kurt Gödel’s letter to von Neumann was never answered. Or was it? The problem solving ability of von Neumann is legendary, so could he have actually proved it long ago? He worked for various secret government agencies, so would they tell us if they really had a proof?

The Supercomputer Fraud. Actually hardware is mostly lights and fakes. Inside is one laptop running a secret very clever algorithm that can solve huge systems of equations fast… OK, here’s another principle: sometimes a special case of a conspiracy theory can be taken seriously.

The Memory Chip Fraud. The number of atoms in the observable universe is believed to be less than , while Planck instants gives a generous 300 billion year timespan for our pocket of the cosmos. Thus every act of storing something to memory in the whole history of our pocket can be coded within 500 bits. Just doubling that leaves a lot of room for error correction and hashing and mirroring. The mathematics involved here has been known since Claude Shannon in the 1940’s. Hence no computer needs more than a single 1K memory chip, let alone Bill Gates’ 640K. The rest is for sales pitches—come on, you don’t really believe your cheap digital camera is storing millions of individual bits in the time it takes to press a button, do you?

OK, this is a joke, but it leads into the next two, which aren’t.

No True Randomness. Every string we write down or read is compressible to, say, 500 or 1,000 bits. That is, all our computing and instrumentation works within the range of strong pseudo-random generators, perhaps in blocks. Strong PRGs are commonly believed to exist. How could we tell the difference? One computer scientist who believes this is Jürgen Schmidhuber.

The Simulation Argument. This is legion in popular culture from “The Matrix” and “Inception” and other sci-fi, so we’ll just refer you to Nick Bostrom’s formulation of it. In theory we could tell the difference if something happened in the manner of The Truman Show where a light labeled “Sirius” falls from the sky. But are there any such events?

We offer one complexity-related observation. Although it is routine to say that classes like and have universal simulation, this isn’t strictly true. The universal function for doesn’t belong to —if it did, then would be in some fixed polynomial time bound, which it isn’t. Although proving this is technically murkier for “random” or “promise” classes like , the essential idea holds for any reasonable complexity class. Thus a universal simulation involves dropping down to a lower grade than the resources on which you draw. If our universe is convincingly universal, perhaps this is a well-motivated reason to reject the argument.

Computer Chess Fraud. Ironically the highest-level accusation wasn’t against a human for cheating with a computer, but rather against a computer for cheating with a human. Garry Kasparov accused IBM’s Deep Blue of making moves with “deep intelligence and creativity” that could only come from a human, presumably Ken’s friend Grandmaster Joel Benjamin. Kasparov demanded to see the logs of Deep Blue’s calculations of a particular move that was later revealed to be far from best, even though it caused Kasparov to resign a game where he still had considerable drawing chances. When IBM refused, the conspiracy theory took off, and might have done so even without Kasparov’s fanning—it still percolates to this day even though the logs were later posted.

Today it is easy for anyone to test the moves with inexpensive—even free—chess programs that are apparently stronger than Deep Blue was, even running on cheap hardware. In several of Ken’s tests the aforementioned disputed move, 45.Ra6 in Game 2, looks good until fairly high depth when it suffers a big swing down in value. Such a swing may be an unlikely event, but the tests give a natural explanation that Deep Blue probably didn’t sense the swing in time. Here is a graphic of one of Ken’s tests, showing the Rybka 4.1 program at depth 18 after the swing down.

Incidentally Ken is not convinced by the analytical conclusion stated here that Kasparov didn’t have a draw when he famously resigned. He believes the 51.Ra1 move given there can be met by 51…Kf8, and after 52.Qc7, the slinky 52…Kg8. Black may have to lose several pawns in exchange for White’s advanced d-pawn, but then Black gets counterplay by pushing the e-pawn. (The move 45…h5 wasn’t played—Ken inserted it to overcome an off-by-one bug in the Arena chess GUI’s automatic-analysis routine.)

Barney Google. With the goo-goo-googly eyes…tracking all activity on your PC or at least what’s relevant to commerce, and ingesting data. Could this be undetectable by everyone? Making an undetectable Trojan might just be the flip side of the wicked problem of designing a completely secure OS.

Open Problems

Do you believe in any of our ten conspiracy theories? Do you have your own? What are they?

[revised TSP film’s Wikipedia critical-reception link—now has others besides us]