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?

${\bullet }$ 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?

${\bullet }$ 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.

${\bullet }$ 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?

${\bullet }$ 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.

${\bullet }$ The Memory Chip Fraud. The number of atoms in the observable universe is believed to be less than ${2^{270}}$, while ${2^{206}}$ 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.

${\bullet}$ 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.

${\bullet}$ 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 ${\mathsf{P}}$ and ${\mathsf{BQP}}$ have universal simulation, this isn’t strictly true. The universal function for ${\mathsf{P}}$ doesn’t belong to ${\mathsf{P}}$—if it did, then ${\mathsf{P}}$ would be in some fixed polynomial time bound, which it isn’t. Although proving this is technically murkier for “random” or “promise” classes like ${\mathsf{BQP}}$, 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.

${\bullet }$ 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.)

${\bullet }$ 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]

1. June 28, 2012 12:44 am

I once made the following remarks regarding Osama Ben Laden’s killing by a US special operation team:
* For all we (as in we, the general public) knew at the time, Osama Ben Laden could have been dead for quite a while, due to illness or other reasons.
* Neither Al Qaeda nor the US had an interest in publishing such information: the former because such an organization benefits from the story of the charismatic chief escaping all attempts on his life, the second because it is not good for public relations to admit you were spending billions about killing a man who was already dead.
* In contrast, the US had an interest in appearing to kill Ben Laden: not only does it signal to the world that anyone on the planet, however well hidden, will not escape the US’ wrath, it also makes a good case for withdrawing from Afghanistan with an appearance of victory. The Afghan war is unpopular and costs billions and billions and many lives; the Obama administration has an interest in withdrawing in a victor’s posture.

Therefore, it seems not impossible that the Osama Ben Laden was already dead before the raid and that the raid was staged so as to provide the Obama administration with a victory. I do not believe it was the case, but at least it is not impossible and the hypothesis cannot be quickly dismissed.

The only facts we have, as far as I know, is president Obama’s word. The reason why we believe the raid took place is that we generally rather like president Obama. Yet, we should remember the Gulf of Tonkin incident and the “weapons of mass destruction” in Iraq: it is not unheard of that senior US officials lie to the world in order to pursue war objectives. Richard Nixon is also a good example of a US president caught in a web of deception.

June 29, 2012 11:54 pm

Al Qaeda would be easily able to expose such a lie, thus discrediting the US government.

July 3, 2012 1:52 pm

It’s more plausible that OBL is still alive, being subjected to enhanced interrogation of some kind, since AQ would have no way to disprove that and probably wouldn’t even know about it. But I wouldn’t bet on it.

Alternatively, it’s possible that OBL died of natural causes under the protection of the ISI, we found out about it, and the whole raid was some kind of scam. Again, this isn’t the way to bet, but I don’t see how we could distinguish the official story from either of these from available information.

June 30, 2012 9:38 am

“The raid was made by a limited cadre of elite soldiers sworn to secrecy.”
Remember the whole team of elite soldiers died when their helicopter crashed. And we know that dead people do not speak.

July 3, 2012 12:22 am

You’re wrong. I have friends in the Navy, specifically ST6, and our friends died in that crash. The men who died in the blackhawk crash were NOT part of that raid. How dare you allude to them dying for a coverup of some half-baked conspiracy theory.

2. June 28, 2012 12:47 am

(I realize the above theory is not about theoretical computer science. I mention it because it illustrates something that theoretical computer scientists are well aware of: that one should always be aware of the hypotheses that are used in order to reach a conclusion, and were they come from.)

June 28, 2012 4:46 am

If P=NP then comedic possibilities become near-certainties … per “On the unexpected efficacy of SAT solvers” (Bulletin of the AMS, April 1, 2020).

June 28, 2012 6:54 am

My favorite conspiracy theory: The entire internet is controlled by the Illuminati.

June 28, 2012 9:03 am

Craig,

Great example.

June 28, 2012 12:39 pm

Of course, you know that the whole the purpose of the internet is to keep the “sheeple” busy watching conspiracy theory videos on youtube, while the Illuminati secretly take over the world.

• June 29, 2012 7:40 pm

Yes!!! Not internet only! One day you can receive a message with Code, that code will stop your OS and CPU.

June 28, 2012 7:39 am

A chess-themed conspiracy narrative that has enjoyable complexity-theoretic overtones is Ian Watson’s novel Queen Magic, King Magic.

Watson’s novel theme is (spoiler alert) the “burning arrow” discovery/realization by the individual chess pieces that they have the power to alter the rules of their own game, and even the power to enter-and-alter other games … including our game as human chess-players. Recommended. 🙂

6. June 28, 2012 9:27 am

I always thought that it was well-known that there was no true-randomness. For example: the Schrodinger equation is deterministic. Thus the wave-function of the universe also is deterministic. Result: no true randomness. 🙂

• June 28, 2012 10:18 am

I read that by analogy with NFA-to-DFA. The Schrödinger equation describes the DFA, but we experience one computation by the NFA in “frog’s-eye view” mode, and that can involve true randomness. If “Many Worlds” is true then others might be experiencing other computations.

Another way to get true randomness is locally, a-la this paper by Max Tegmark. But IMHO you need there to exist 2^n bits of “stuff” in order to get n random bits that way, and that strikes me as excessive.

• June 28, 2012 11:25 am

Isn’t the “frog’s-eye view” perspective just an attribute of reducing the context in consideration? That is, the non-determinism in an NFA is there at the choice of when to change states, but if we pull back somewhat, the overall ‘system’ is in fact deterministic?

Paul.

• June 28, 2012 12:38 pm

“Pulling back” could be a 2^n expansion, which I think stays virtual, not real. Further analogy: when matching to a regular expression with grep the DFA never gets built, and what is actuated is a path thru the NFA.

• June 29, 2012 11:11 am

I was having one of those ‘moments’ when I wrote this:

but oddly, the part where I talk about how information is a serialization of the underlying complexity seems to fit well with what Max Tegmark is saying in the initial part of his paper (I haven’t had time yet to read the whole thing).

In his sense, the universe is a fairly simple formal system governed by basic rules, and it’s the interaction of the epiphenomenon that form the microscopic superpositions. Taking a path through that provides information whose complexity is tied to its traversal. But taken as a whole, with a normalized path is far less information in the system.

In that sense random is not applicable to the underlying macroscopic superpositions, but rather to the twists and turns of the path as we choose to observe it. So in a sense although the DFA’s don’t need to be build explicitly in grep, they are still the controlling factor for the behavior of the seemingly non-deterministic path in the NFA?

Or is it another one of those ‘moments’ 🙂

Paul.

7. June 28, 2012 11:16 am

Isn’t factoring really easy? You just post a question somewhere on the Internet asking for the factors for any given number, head off to a bar and then wait for someone to answer it 🙂

I kinda wish everything were a simulation, then at least it would make some kind of sense …

Paul.

8. June 28, 2012 5:34 pm

My favorite theory conspiracy is:

I’ve solved P vs. NP (www.andrebarbosa.eti.br/P_different_NP_Proof_Eng.pdf) but the Theoretical Science community hides this breakthrough because I’ve discovered also that the Cook-Levin Theorem is false.

9. June 29, 2012 11:49 am

“Quantum Computers Already Exist” – I think one could one-up this by additionally claiming that quantum computing skeptics are really CIA (or Mossad/Chinese inteligence/…) plants aiming to disrupt the progress in the field while the US military has already built a quantum computer.

June 29, 2012 2:21 pm

For elaboration on the theory that intelligence agencies or others are accumulating but not publishing bugs, see http://www.forbes.com/sites/bruceschneier/2012/05/30/the-vulnerabilities-market-and-the-future-of-security/

11. July 2, 2012 5:53 am

We should add “shaped charges and millisecond timing are not necessary for CD” to the list.

or point out that they are.

July 2, 2012 2:30 pm

Conspiracies are hard to pull off because the world is complex place, an obstacle course of caveats for the hapless conspirator. A prime example that I’m in a good position to comment on: The break of the “RSA token system” you mention, by which attackers have “dented the system if not destroyed it.”

Could this vulnerability have remained hidden for years, exploited by the Knights Templar or the Rosicrucians or (given their affinity for attacking RSA: bit.ly/LfVxFv) a cult of neo-Pythagoreans?

Perhaps, except that…

The RSA token system, in the sense of the well known authentication technology, wasn’t broken, or even dented. What was broken was a token model (SID 800) that “wrapped” keys under the RSA algorithm itself. It was the RSA algorithm that came under attack, not the SecurID algorithm.

But then it wasn’t really the RSA algorithm itself that was attacked—rather (as Matt Green writes) a particular implementation (padding) using a vulnerable RSA encryption standard called PKCS #1 v1.5.

Could this vulnerability, then, have remained secretly in recent years in the hands of a cabal of conspirators?

Perhaps. Except that a researcher named Daniel Bleichenbacher published it in a well known paper in 1998. And RSA itself published a fix to the vulnerable standard as well, in the form of PKCS #1 v.2, also back in 1998.

So conspirators in this case wouldn’t be using secret knowledge to achieve their ends. Rather, they’d be relying on knowledge that’s been public and remediated, in principle, for well over a decade. They’d be exploiting an engineering lapse or inadvisable attempt at backward compatibility by RSA and other security vendors, rather than an ultra-secret backdoor.

Additionally, the opportunity for exploitation of the SID 800 is somewhat limited in practice. An attacker must have possession of the device itself and knowledge of its user’s PIN to mount the attack. Without getting into details, in most deployments of the token, an attacker with the device and PIN generally has no need to mount the Bleichenbacher attack to begin with to compromise a system. I don’t have details on other devices implicated in the CRYPTO paper, but suspect the case is similar.

So a Rosicrucian or neo-Pythagorean cult worth its salt would probably have looked for some other way to exert clandestine dominion over the world’s uninitiated masses. Angry Birds, maybe?

13. July 5, 2012 3:02 pm

In fact, Dan Brown already in 1998 wrote in “Digital Fortress” about NSA supercomputer TRANSLTR deriving “its power … from new advances in quantum computing …”.

14. July 12, 2012 12:23 pm

Its always great to see conspiracy news!