Farewell to The Economist

An Email I sent this weekend:

To: customerhelp@economist.com
Subject: Please cancel my subscription

My Customer Reference Number is …
My address is: …

I have been a subscriber for more than two decades, but your latest cover story (“Globalisation and Politics: The new political divide”) is pure propaganda that I have no interest in financing.

I am saddened to see the decline of a once great publication.

I will be donating my refund to the Trump campaign.

Aside from Technology Review (which is free), The Economist is the only magazine to which I still subscribe after all these years. Or rather, it was.

I am not naïve. As a long-term subscriber, I am well aware of The Economist’s leanings and how they differ from my own. But I expect them to display some vague understanding of both sides of contentious issues, and then to argue their case with facts and intelligent reasoning. Smart people disagreeing with me are among my favorite things to read.

But this… is such blatant and ridiculous propaganda that I am not even sure where to begin a critique. It simply mocks itself from beginning to end.

Oh what the heck; since it is likely the last Economist article I will ever read…

Farewell, left versus right. The contest that matters now is open against closed

There it is, right from the get-go. The proper and well-known terms in this context are “nationalism” and “globalism”. And it is not as though “nationalism” has universally positive connotations; at least, not yet. But just to make sure, they chose value-laden terms tangential to the debate. I mean, really, how could any reasoning person prefer “closed” to “open”? Checkmate!

So far, Britain’s decision to leave the European Union has been the anti-globalists’ biggest prize: the vote in June to abandon the world’s most successful free-trade club

Wait, do you mean the super-state with its own flag, anthem, and barely-elected rat-faced bureaucrats hostile to the very concept of nation states whose edicts on every topic (including immigration) override national parliaments? That “free-trade club”?

was won by cynically pandering to voters’ insular instincts

I see. So apparently Brexit won because UK voters were tricked into thinking trade is bad.

Listen, you disingenuous mouthpieces, the UK voted out precisely because the EU is not remotely a “free-trade club” and the electorate knows it. Does that scare you? I think it scares you.

On July 26th two men claiming allegiance to Islamic State slit the throat of an 85-year-old Catholic priest in a church near Rouen. It was the latest in a string of terrorist atrocities in France and Germany. The danger is that a rising sense of insecurity will lead to more electoral victories for closed-world types. This is the gravest risk to the free world since communism. Nothing matters more than countering it.

In other words, the biggest threat posed by Islamic fundamentalists hell-bent on annihilating the people and culture of the West, and who have shown the willingness and ability to infiltrate our societies, is that the wrong kind of politician might get elected.

I have honest-to-god seen parody accounts make this argument more convincingly.

Even so, for Mr Trump to urge Russia to keep hacking Democrats’ e-mails is outrageous.

This is the point where I decided to cancel my subscription.

What Trump has done throughout his campaign — and I mean throughout — is called “trolling the media”. Here is how it works. Trump makes a statement, no matter how ridiculous, and the media reaction is invariably even more ridiculous. (Note: Image is exaggerated but not by much.) The result is free publicity and usually a bump in the polls. It has been fascinating to watch.

This instance was not even very subtle. “Hey I hear Russia has Hillary’s deleted Emails. Maybe they should give them to the FBI!” That’s all? Seriously?

My personal theory for why it works (and keeps working) is that journalists are morons. But I expected better from The Economist.

Sigh. I am bored now, so go read the rest yourself. See if you smile like I did at the word “worryingly”.

Oh, and do not miss the comments sorted by recommendations. I like the one saying that the wall in the cartoon should have a sign reading “Please Use The Door”.

Hillary (4) – Totally Exonerated

I decided it would be fun to go through portions of FBI Director Comey’s statement and paraphrase.

Note that he did not have to provide so much… detail. In fact, he did not have to say anything at all. During his delivery, he seemed to add special emphasis each of the numerous times he directly contradicted some public statement of hers. But perhaps that is my imagination.

Our investigation looked at whether there is evidence classified information was improperly stored or transmitted on that personal system, in violation of a federal statute making it a felony to mishandle classified information either intentionally or in a grossly negligent way, or a second statute making it a misdemeanor to knowingly remove classified information from appropriate systems or storage facilities.

“Bear in mind the phrase ‘grossly negligent’.”

Secretary Clinton used several different servers and administrators of those servers during her four years at the State Department, and used numerous mobile devices to view and send e-mail on that personal domain.

“Remember when she said she used a personal server to avoid having multiple devices? She lied.”

From the group of 30,000 e-mails returned to the State Department, 110 e-mails in 52 e-mail chains have been determined by the owning agency to contain classified information at the time they were sent or received.

“Remember when she said she never sent nor received classified information? She lied.”

“Remember when she changed her story to never having sent nor received information that was classified at the time? She lied.”

The FBI also discovered several thousand work-related e-mails that were not in the group of 30,000 that were returned by Secretary Clinton to State in 2014.

“Remember when she said she had returned every Email ‘remotely related to work’? She lied.”

Although we did not find clear evidence that Secretary Clinton or her colleagues intended to violate laws governing the handling of classified information, there is evidence that they were extremely careless in their handling of very sensitive, highly classified information.

“Can you distinguish ‘grossly negligent’ from ‘extremely careless’? Me neither. Thanks for paying attention.”

None of these e-mails should have been on any kind of unclassified system, but their presence is especially concerning because all of these e-mails were housed on unclassified personal servers not even supported by full-time security staff, like those found at Departments and Agencies of the U.S. Government—or even with a commercial service like Gmail.

“Commercial services like Gmail, with full-time security personnel, are completely pwned by all competent intelligence agencies. So seriously, what chance do you think a piece of shit Exchange server set up by some loser I.T. monkey has?”

But even if information is not marked “classified” in an e-mail, participants who know or should know that the subject matter is classified are still obligated to protect it.

“Remember when she changed her story to having never sent nor received anything ‘marked’ classified? Such markings are not required, so she misled.”

Only a very small number of the e-mails containing classified information bore markings indicating the presence of classified information.

“Also she lied.”

With respect to potential computer intrusion by hostile actors, we did not find direct evidence that Secretary Clinton’s personal e-mail domain, in its various configurations since 2009, was successfully hacked.

(He could have stopped right there, but…)

But, given the nature of the system and of the actors potentially involved, we assess that we would be unlikely to see such direct evidence.

“We do not know how many foreign adversaries hacked her system, because a piece of shit Exchange server set up by some loser I.T. monkey does not even keep adequate logs for that determination. As a result, we will never know the full extent of the damage.”

We do assess that hostile actors gained access to the private commercial e-mail accounts of people with whom Secretary Clinton was in regular contact from her personal account. We also assess that Secretary Clinton’s use of a personal e-mail domain was both known by a large number of people and readily apparent. She also used her personal e-mail extensively while outside the United States, including sending and receiving work-related e-mails in the territory of sophisticated adversaries. Given that combination of factors, we assess it is possible that hostile actors gained access to Secretary Clinton’s personal e-mail account.

“If you think there is any chance Russia and China do not have every bit of data from every one of her servers, you are an idiot.”

In looking back at our investigations into mishandling or removal of classified information, we cannot find a case that would support bringing criminal charges on these facts.

“Despite being a clear violation of statute, this sort of reckless incompetence is not usually punished by jail time.”

(Again, he could have stopped there, but…)

To be clear, this is not to suggest that in similar circumstances, a person who engaged in this activity would face no consequences. To the contrary, those individuals are often subject to security or administrative sanctions.

“However, anyone else who did a fraction of this would never again be allowed to so much as sweep the floor in a secure facility.”

So, what is the take-away headline? HILLARY CLEARED OF ALL CHARGES! I am sure that is what he was aiming for.

Hillary (3) – Child rape cases are a hoot

You might want to start with the background article.

Summary: Hillary successfully defended a child rapist — oops, I mean “accused” child rapist — back in 1975. But that is not the interesting part. The interesting part is this interview:

Note that this is raw source material. No pundits; no shills; no conspiracies… Just Hillary Rodham, in her own words.

Now, I can already hear you blathering something about adversarial justice systems, so I will pause to let you finish.

There, are you done? Good. Yes, yes, I understand the right to counsel. I understand that it is better to let ten guilty men go free (or was it 100?) than to punish one innocent. I understand the argument that, if you rape a 12-year-old girl but the prosecution mishandles your underwear with her blood on it, that you “should” walk. I do not necessarily agree, but I certainly understand the argument. So let’s say we stipulate all of this.

This interview is still incredibly damning, not for what it says about the case, but for what it says about the state of mind afterward.

Some of us would have trouble defending an accused child rapist. If we accepted the case and came to believe our client was guilty, many of us would have trouble proceeding. If we proceeded anyway and won, almost all of us would have mixed emotions at best. We would not later reminisce about it, and boast about it, and laugh about it. We would not say in an interview, “Lawdy, I had some tough cases in those days! I remember this one child rapist yuk yuk yuk … and I got him off with time served! Ah, memories.” We would be incapable of this because of that little voice in our head; you know, the one that distinguishes right from wrong? That little voice would constantly be whispering, “Dear God, he RAPED that little girl and I helped him go free.”

A few people are born without that little voice. We call them “sociopaths”. This recording demonstrates that Hillary lacks that little voice.

But please, do not take my word for it. Do not let me, or anyone else, tell you what to think. Listen for yourself, and draw your own conclusions.

Prediction markets and Brexit

My day job leaves little time for blogging, but I want to get this down before the whole topic is history.

The Brexit referendum begins in just a few hours. The Leave side was showing momentum prior to the murder of Jo Cox, but since then, pretty much all polls have been stuck at “too close to call”.

Prediction markets, on the other hand, have indicated a bias against Leave regardless of the polls. As I write, they give Leave just north of a 25% chance.

The question is, why are the polls and the prediction markets so different?

This morning, Zero Hedge (I know, I know, bear with me) published a very interesting article pointing out that the Remain bets are fewer in number but larger in dollar amount.

In a brief Twitter exchange, JC Kommer reminded me that it is normal for the bet sizes to skew as the odds shift. (This is simple math; for a $1 payout at a 25% probability, one side has to put up $0.25 and the other $0.75.) But the skew here is significantly larger than 3:1… So it is demonstrably true that the Leave odds are being pushed down by a comparatively small number of large bets.

When I mention this to family and friends, some say that it is not surprising, since relatively small amounts of money can move these markets around. Remember 2012?. But I am not so sure in this case. Betfair alone has over $70M in matched bets on the referendum, and thanks to arbitrage, manipulating any prediction market requires pushing on all of them combined.

I can think of a few reasons the Big Money might be betting against Leave. Maybe they are the same as the Smart Money, and the prediction markets are just doing the efficient thing. Or maybe they prefer Remain and think that manipulating these markets can tilt the balance in the real world; cf. reflexivity. (People do prefer to vote with the winning side.) Or maybe they are trying to manipulate other assets indirectly, several of which are heavily correlated with these markets.

Of course, these explanations are not mutually exclusive, and I do not ever expect to know for sure. But the bias of the Big Money is surprisingly visible. In the future, I expect they will use a large number of small bets to hide this sort of tell.

[Update 2016-06-23 16:30 EDT]

Betfair now shows $97M in matching bets with Leave at 14%.

[22:12 EDT]

$137M in matched bets, odds essentially 50/50. Holy crap.

Tonight is basically God’s stop hunt

Hillary (2)

OK, full disclosure: I do not like Hillary Clinton. Actually, I think the Clintons are sociopaths. Literally. Both of them.

Of course, I could be wrong. I am fully aware that most of what I believe is the result of deliberate propaganda. Just like most of what you believe.

That is why I look for stories that I can evaluate based on my own direct, personal knowledge. In that spirit, from all the wonderful Clinton stories over the years, I want to discuss just two.

The first is the cattle futures incident. I am sufficiently familiar with markets to know that there is only one way to turn $1,000 into $100,000 over ten months of trading cattle futures, which is illegally. I do not know why someone wanted to transfer $100,000 under the table to the wife of the governor of Arkansas; I just know that is what happened. This is not propaganda. This is not partisanship. This is mathematics.

You can argue the late 70s was a long time ago. Certainly, the relevant statutes of limitations have long since expired. But she never admitted any wrongdoing. That makes this an ongoing lie, which makes it current and therefore relevant.

The second story, naturally, is the Email server. I know quite a lot about Email servers. For example, I could code one. And the operating system on which it runs. And design the hardware. Anyway, I know there is only one reason a sitting cabinet official routes all of her electronic communications through a server in her basement, which is to keep them away from people with legal authority to view them (e.g. law enforcement or the Judicial branch). And I know that any claim to the contrary — such as “it was a matter of convenience” — is a lie.

I really do love this story because my personal knowledge in this area is orders of magnitude greater than any journalist’s. So whenever I read an article about Hillary’s email server, I do not learn anything about Hillary’s email server; I learn something about the author of the article. For example, when I read someone calling it a “personal Email account” rather than a “personal Email server”, or comparing it to Colin Powell’s AOL account or whatever, I know I am reading a partisan hack making a lame attempt to deceive stupid people. (Or just a really stupid journalist. It can be hard to tell the difference.)

The Hillary campaign says her arrangement was allowed by the rules at the time. That might or might not be true; with the Clintons, you never know. But assuming it is true, that is only because the rules at the time did not contemplate something so ridiculous as a sitting cabinet official routing all of her electronic communications through a server in her basement.

Which brings us to the felonies. Classified data is another area where I actually know something. Dating myself a bit, once upon a time I internalized the Orange Book and several of its interpretations. I know all about mandatory access controls and covert channel analysis and formal verification methods… In short, I am very familiar with the difference between the kind of system that processes classified information and the kind of system you get when you ask some pathetic I.T. monkey to set up an Exchange server in your basement.

I am not a lawyer. But I do know that there is only one way for top secret codeword information to migrate from an authorized to an unauthorized system, which is illegally. Based on facts already published, I know that someone, somewhere committed a felony. I do not know exactly who, or exactly which felony, because there is more than one possibility. (My own suspicions would start with Huma Danger, née Abedin.) But I am 100% certain that someone committed a crime.

I do not expect anyone to be held accountable, of course, since in our system we are all very much unequal under the law. These crimes will never approach indictment. The generous explanation is that there is a difference between proving some felony occurred and convincing a jury that a specific person committed a specific felony. The realistic explanation is that the Obama administration does not prosecute its friends.

She will be the nominee and most likely President. Tens of millions in financial sector donations buys a lot of hack journalism, and the fix is in. More on that in another installment, perhaps. Although I might need to get drunk first.

Hillary (1)

I read with some amusement the Boston Globe’s endorsement of Hillary Clinton. You would think a 1000-word endorsement by a major newspaper touting someone’s “experience” and “seasoning” would mention one or more of her accomplishments. Things she has actually, you know, done.

The New York Times endorsement makes an attempt, which winds up being even more funny. She “brought star power” to the Department of State! She “helped make it possible” (for her successor) “to impose tougher sanctions on Iran”! (Whatever that means.) She “worked to expand and deepen the dialogue with China”!

But flying around the world on the taxpayer’s dime is not an achievement. Talking is not an achievement. Giving speeches to Goldman Sachs for $300,000 is not an achievement.

Intellectually honest liberals know that she is corrupt. They know her chief accomplishment as Secretary of State was to ruin the Middle East. Further ruin, I mean. Remind me again, how is Libya doing? (Of course, this might be no accident. Perhaps there is some nation, somewhere, in whose interest it is to have the bulk of the Middle East be a sea of ungovernable anarchic clusterf*cks? Just not the U.S.)

These endorsements say so much more about the Globe and Times editorial boards than they do about Hillary Clinton. It is frankly refreshing to have it be so blatant.

That said, I am pretty sure she will win the nomination and the Presidency for the simple reason that Goldman Sachs needs a return on their investment.

Great Scots!

(I could really use some whiskey for this post)

So, the U.K.’s political/financial leadership — and their journalist microphones — are getting downright apocalyptic about the possible consequences of Scottish independence.

That alone would be enough to get me out voting “yes”, were I a resident of Scotland. Alas, I am not. But I do know the only poll I need to follow:

Betfair Scottish independence contract

It is not quite as easy to read as TradeSports (RIP), in part because you have to translate “Back” and “Lay” from English to English. Roughly, “back” means “bet for” and “lay” means “bet against”. The number represents gross winnings versus a “back” bet of $1. (Technically it’s £ not $ and occurs in multiples of 10. But (a) I am from the colonies and (b) the units are irrelevant.)

For example, as I write, the “yes” contract is trading at 4.6/4.7. That means you can hand over $1 and get back $4.60 if Scotland votes for independence, or you can hand over $3.70 and get back $4.70 if Scotland votes against independence.

Bottom line: To convert Betfair lines to probabilities, just take reciprocals. So 4.6/4.7 corresponds to a probability between 21.3% (1/4.7) and 21.7% (1/4.6). That is higher than I would estimate, personally. Anyway “too close to call” is a bit generous.

Just like TradeSports, the nice thing about this market is that it reflects new information very quickly. This particular contract was trading around 3.0 a week ago.

Other contracts of mild interest:

2014 Senate control (Republicans currently at 1.5 = 67%; usually agrees with FiveThirtyEight)
2016 Democratic nominee (currently Clinton 67%)
2016 Presidential election (currently Clinton 40%; I myself would estimate these last two to be equal and higher)

Cryptography Part 4: Random numbers

Executive summary: There are no random numbers; only random number generators.

If that sentence made perfect sense to you, feel free to skip this installment. Otherwise, read on.

In the previous post, we saw a cryptosystem whose security was entirely based on a coin toss. But why use a coin? Why not just get together and agree that when I say one thing I will mean another?

Well, two reasons. First, humans are notoriously predictable; our minds are just not very good at being random. Second, ad-hoc cryptosystems are impossible to analyze mathematically, and mathematical certainty is our goal (even if we will not quite get there).

Randomness lies at the heart of all cryptography, both in theory and in practice. So we want to be able to think about it clearly.

But wait a minute. What is a “random number”, exactly? A single number is just itself, so what does it even mean to call it “random”? After a coin lands, it is either heads or tails, neither of which seems particularly “random” on its own. And so on.

The solution to the dilemma is this: “Random” refers not to values, but to means of generating them. It is not the outcome of the coin toss that is random, but the process of flipping it.

So, when you see the phrase “random number generator”, do not read it as “random-number generator” (i.e., a generator of random numbers). Read it as “random number-generator” (i.e., a random generator of numbers). The randomness is in the generator, not in the numbers.

Even experts often speak loosely here, using phrases like “source of random bits” when what they really mean is “random source of bits”. Don’t let them confuse you. Or themselves.

Aside: If you show this post to a mathematician and they mumble something about “Martin-Löf randomness” or “Kolmogorov complexity”, do me a favor and smack them upside the head. This is cryptography, which means computers, which means our world consists only of integers like God intended.

Aside #2: If you show this post to a physicist and they mumble something about “Schrödinger”, or to an engineer and they mumble something about “thermal noise” or “reverse-biased diodes”, do me a favor and smack them upside the head twice. Actually, make it three times for the engineer. To win against someone who can outsmart us, we need very precise reasoning, which means totally separating the math from the real world. We have to bring them back together eventually, of course, but leaving them connected during the process will only make our thinking fuzzy and our proofs non-existent. (This is the problem with the Linux /dev/random design, by the way… But that is a topic for another time.)

The mathematical language of randomness is called probability theory. In that language, my summary statement would read: There are no random events; only random distributions. In basic cryptography, the formal proofs tend to be tedious but straightforward, relying only on very elementary probability theory. We shall see how far I can get in this series without it.

More next time.

Cryptography Part 3: Once upon a bit

I recently completed Dan Boneh’s introductory cryptography course. I will probably wind up covering some subset of it here, but at my own pace and in my own way. If you want a more serious treatment, go watch his lectures.

As usual, if the equations below look like roadkill, click through to the actual post.

I like simple examples, so let’s start with one. Suppose I am about to go to New York City to obtain some inside information on a public company. When I have the information, I plan to send you one of two messages: “Buy” or “Sell”.

Let’s say we have an adversary who is very smart and very resourceful. He knows our plan. He can and will intercept whatever message I send to you. Can we arrange to communicate in a way that reveals nothing to him?

Here is one approach. Before I head off to New York, we get together in a closed room. We put our cell phones in the refrigerator, activate our Cone of Silence, line the walls with tin foil, etc. And then we flip a fair coin. If the coin comes up heads, we agree that I will lie when I send you the message; that is, I will say “Buy” when I mean “Sell” and vice-versa. If the coin comes up tails, we agree that I will say what I really mean.

Remarkably, this simple scheme guarantees that no adversary can learn anything from my message. Thanks to our use of a random coin, our adversary has a 50/50 chance of understanding my message correctly no matter how he interprets it. Put another way, the adversary can guess the outcome of our coin toss with even odds… But he can also guess my intended message with even odds, without even bothering to intercept anything! So my message tells him nothing he did not already know, which means he obtains zero bits of information from it.

This example, simple though it is, illustrates several fundamental concepts in cryptography.

First, we have the set of possible messages I want to communicate to you, customarily called the message space and denoted by \(\mathcal{M}\). In this example, \(\mathcal{M} = \{Buy, Sell\}\). In real-life cryptosystems, \(\mathcal{M}\) would be considerably larger; something like “all possible English paragraphs”, for example.

Second, we have an adversary whose capabilities are bounded and well-specified. (An adversary with unbounded capabilities is unbeatable; an adversary with ill-specified capabilities defies sound analysis.) Note that the general idea in serious cryptography is not to ask “What can the adversary do?”, but rather to ask “How powerful can the adversary be and still permit us to win?” In this example, we assume our adversary has unlimited computational power, unlimited eavesdropping power, and total knowledge of our plans. We assume he lacks knowledge only of the outcome of our coin toss. We also assume he can only eavesdrop, and not (say) tamper with my message en route to you. Subject to these assumptions, we can prove that my communication to you is perfectly secure in the sense that it communicates no information to our adversary.

Third, we have some set of possible messages I might actually transmit and the adversary could intercept. This is called the ciphertext space and is denoted by \(\mathcal{C}\). In this example, the ciphertext space is the same as the message space; that is, \(\mathcal{C} = \{Buy, Sell\}\).

Fourth, we have some secret information, shared by us but unknown to our adversary, that we will use to encode elements of \(\mathcal{M}\) into elements of \(\mathcal{C}\). The set of all possible secrets is called the key space and is denoted by \(\mathcal{K}\). In this example, \(\mathcal{K} = \{Tails, Heads\}\).

Note that we assume our adversary knows absolutely everything about our scheme except for the key. This has been the customary assumption in cryptography for over a century, and it is called “Kerckhoff’s Principle”.

Fifth, we have an encryption scheme, denoted \(E\). This is a function that takes a (key, message) pair and computes a ciphertext. That is, \(E\) takes some \(k \in \mathcal{K}\) and some \(m \in \mathcal{M}\) and produces \(E(k, m) = c \in \mathcal{C}\). In this example:

$$E(Tails, Buy) = Buy \\
E(Tails, Sell) = Sell \\
E(Heads, Buy) = Sell \\
E(Heads, Sell) = Buy$$

The encryption scheme tells me how to encode a message to you.

Sixth, we have a decryption scheme — denoted \(D\) — that takes a (key, ciphertext) pair and produces a message. That is, \(D\) takes any \(k \in \mathcal{K}\) and \(c \in \mathcal{C}\) and produces \(D(k, c) = m \in \mathcal{M}\). In this example, the decryption scheme is the same as the encryption scheme:

$$D(Tails, Buy) = Buy \\
D(Tails, Sell) = Sell \\
D(Heads, Buy) = Sell \\
D(Heads, Sell) = Buy$$

The decryption scheme tells you how to decode a message from me.

Note that the \(E\) and \(D\) functions must obey the basic consistency principle that decryption is the opposite of encryption. In symbols, for any \(k \in \mathcal{K}\) and \(m \in \mathcal{M}\), \(D(E(k,m)) = m\).

A collection of these five items — \(\mathcal{M}\), \(\mathcal{C}\), \(\mathcal{K}\), \(E\), and \(D\) — is called a cryptosystem. This particular cryptosystem is called the “one-time pad”.

I suppose that is enough for one installment. I will refer back to this example in the next two or three posts, where I plan to cover randomness, the general one-time pad, and more than you ever wanted to know about exclusive-OR. Not necessarily in that order.

Cryptography Part 2: More rambling

Impossibility proofs have always fascinated me. Solving a problem is one thing. Failing to solve a problem is another. But there is something really special about proving nobody can solve it, ever, even if they are smarter than you. (Guess where I am going with this.)

The Delian problem is provably unsolvable. This was not discovered until the 1800s, but the proof is accessible to any mathematically-inclined high school student. So I am going to walk through it. “Seriously, Nemo? You are going to cover an abstract algebra class in a blog post?” Sure, why not?

This will be long, detailed, and almost completely off-topic. Feel free to skip to the last few paragraphs if you just want the punch line.

As usual, if you are reading this in an RSS reader and the equations look like nonsense, click through to the actual post. And ask your RSS provider to install MathJax.

Suppose instead of doubling a cube, we wanted to double a square. That is, given segment AB of length 1, construct a segment of length \(\sqrt{2}\) using straightedge and compass.

Here is one way. Just like last time, draw a small circle centered at B passing through A, then extend AB to cross that circle at C. Draw two larger circles, one centered at A passing through C, the other centered at C passing through A. Let D be an intersection of these larger circles. Draw BD intersecting the small circle at E:

update your browser

Segment AE has length \(\sqrt{2}\).

(Word of advice: Writing raw SVG is a little bit like pulling your own teeth.)

In general, given two segments, it is possible to add, subtract, multiply, or divide them, using only straightedge and compass. That is, if two segments have lengths \(a\) and \(b\), you can construct a new segment of length \(a+b\), \(a-b\), \(ab\), or \(a/b\). Also, given a segment of length \(r\), you can construct one of length \(\sqrt{r}\). I hope these are all plausible enough to leave as exercises (hint: similar triangles).

More interestingly, these five operations — add, subtract, multiply, divide, and square root — are all you can do. To see this requires inventing analytic geometry, which is one reason the Delian problem took 2000 years to resolve. Set up a 2D Cartesian coordinate system with A at (0,0) and B at (1,0). Observe that straightedge and compass constructions involve nothing more than introducing new points by finding the intersections of lines and circles based on existing points. In the Cartesian plane, any line may be described by a linear equation based on two points, while any circle may be described by a quadratic equation based on its center and radius. The coordinates of the intersection of any pair of these (line with line, line with circle, or circle with circle) may be found by solving either a linear or a quadratic equation. Since the quadratic formula involves only addition, subtraction, multiplication, division, and square root, it follows that new intersections of lines and circles can only introduce coordinates based on the coordinates of existing points combined with these five operations.

If you start with segment AB of length 1, and all you can do is add, subtract, multiply, divide, and extract square roots, what lengths can you make? Well, you can add 1 to itself to get 2 by doubling AB. You can add 1 to that to get 3. And so on. So any integer is constructible. You can also divide, so any rational number (that is, any \(a/b\) where \(a\) and \(b\) are integers) is also constructible.

Finally, you can extract square roots. That lets you cover a lot of ground, in some ways. Consider:


This expression involves only integers, multiplication, division, and square root, so its value is constructible with straightedge and compass. And it is close enough to \(\sqrt[3]{2}\) to fool Google Calculator.

Of course, its value is not exactly \(\sqrt[3]{2}\), and neither is any other combination of integers using only these five operations. Proving this takes around three lines if your name is “Galois”, but for me it will take a little longer.

The key to the argument is to ignore square roots for a minute and just think about the four basic operations of addition, subtraction, multiplication, and division. What numbers can you generate starting from 1 and repeatedly applying these?

Obviously, you can generate any integer by adding 1 to itself repeatedly. And you can generate any rational number by dividing two integers.

But that is all you can do. Given any two rational numbers, their sum, difference, product, and quotient are themselves all rational. You cannot “escape” from the rational numbers just by adding, subtracting, multiplying, or dividing, and a mathematician would say the rationals are closed under these operations. Any set of numbers closed under these basic operations — i.e. any set from which you cannot “escape” by addition, subtraction, multiplication, or division — is called a number field, or simply a field. The field of rational numbers is important enough to have its own symbol: \(\mathbb{Q}\). When you see \(\mathbb{Q}\), think “all rational numbers”.

\(\sqrt{2}\) is not an element of \(\mathbb{Q}\); that is, \(\sqrt{2}\) cannot be expressed as the ratio of two integers. The proof of this was known to Euclid, and I omit it here.

To “escape” from the set of rational numbers, let’s try adjoining \(\sqrt{2}\) to them, then combining the elements from that new set with addition, subtraction, multiplication, and division, repeatedly. What numbers can you generate now?

Obviously, you can generate any number of the form \(p + q\sqrt{2}\) where \(p\) and \(q\) are rational. Can you generate anything else?

No. Suppose you have two numbers of the form \(a + b\sqrt{2}\) and \(c + d\sqrt{2}\) where \(a\), \(b\), \(c\), and \(d\) are rational. Whether you take their sum, difference, product, or quotient, the result is of the form \(p + q\sqrt{2}\) where \(p\) and \(q\) are also rational. (Try it.) So numbers of this form are all you can generate; you cannot “escape” just by combining them with the four basic operations. In other words, these numbers — \(p + q\sqrt{2}\), with \(p\) and \(q\) in \(\mathbb{Q}\) — form a field. Mathematicians have a shorthand notation for this field, too; they call it \(\mathbb{Q}(\sqrt{2})\). In math-speak, all elements of \(\mathbb{Q}(\sqrt{2})\) are expressible as \(p + q\sqrt{2}\) where \(p\) and \(q\) are elements of \(\mathbb{Q}\).

We can keep going. Starting from \(\mathbb{Q}(\sqrt{2})\), we can adjoin another element, like \(\sqrt{3}\) or \(\sqrt{1+\sqrt{2}}\). A field created this way, by adjoining a new element to a smaller field, is called a field extension. In general, for a field \(F\), the field extension you get by adjoining an element \(x\) is denoted \(F(x)\).

So, one way to look at straightedge-and-compass constructions is like this. You start with a bunch of numbers from the field \(\mathbb{Q}\). As long as you only add, subtract, multiply, and divide, you stay in that field. The first time you take a square root of a non-square rational number \(\alpha\), you “escape” into the extension field \(F_1 = \mathbb{Q}(\sqrt{\alpha})\). Then, as long as you only add, subtract, multiply, and divide, you stay in that field… Until you take the square root of some non-square \(\beta\) in \(F_1\), at which point you “escape” into the field \(F_2 = F_1(\sqrt{\beta})\).

And so on. Any straightedge-and-compass construction generates a tower of fields \(F_1, F_2, \ldots\), where each \(F_n\) is created by taking a square root in \(F_{n-1}\) and adjoining it. (We define \(F_0 = \mathbb{Q}\).) All numbers in \(F_n\) are expressible as \(p + q\sqrt{r}\), where \(p\), \(q\), and \(r\) come from the previous field \(F_{n-1}\) and \(r\) is not a perfect square in \(F_{n-1}\). Numbers appearing “for the first time” in \(F_n\) — that is, appearing in \(F_n\) but not \(F_{n-1}\) — have \(q\) non-zero.

Now, suppose some straightedge-and-compass construction could generate \(\sqrt[3]{2}\). Then either \(\sqrt[3]{2}\) would be rational — which it isn’t — or it would appear for the first time in some \(F_n\) and therefore be expressible as \(p + q\sqrt{r}\), where \(p, q, r\) are from \(F_{n-1}\), \(r\) is not a perfect square in \(F_{n-1}\), and \(q\) is not zero.

So let \((p + q\sqrt{r})^3 = 2\). Expand that binomial and collect terms to find:

$$(p^3 + 3pq^2r) + (3p^2q + q^3)\sqrt{r} = 2$$

Observe that the coefficient on \(\sqrt{r}\) — that is, \(3p^2q + q^3\) — must be zero. If it were not, we could solve this equation for \(\sqrt{r}\) in terms of values from \(F_{n-1}\), which would make \(r\) a perfect square in \(F_{n-1}\), meaning we never “escaped” from that field at all, a contradiction.

It follows that \(p – q\sqrt{r}\) is also a cube root of 2; just take this value, cube it, and compare to the expression above, remembering that \(3p^2q + q^3\) is zero.

But, since \(q \neq 0\), \(p + q\sqrt{r}\) and \(p – q\sqrt{r}\) are distinct real numbers. Since cube root is a strictly increasing function, every real number has exactly one real cube root. Thus we have reached a contradiction and \(\sqrt[3]{2}\) is not constructible.

The impossibility of the Delian problem was first proven by a guy named Pierre Wantzel in 1837, but the underlying math was found by Galois who was building on Gauss. (“Who was the greatest mathematician, Gauss or Euler?” is sort of the math geek equivalent of “pirates vs. ninjas”. Except that ninjas are obviously way cooler.)

I stole this particular proof from the greatest general-interest math book of all time.

Thus ends this brief introduction to abstract algebra.

What is the point? There are two.

First, if you really want to understand cryptography, you could do worse than to learn a little abstract algebra. Our adversary knows a lot of abstract algebra, and it shows up in most of the mathematical gadgets used for cryptography, especially public key systems. This is not the last time we will see the word “field”.

Second, since our adversary is smarter, more motivated, and better funded than we are, we really, really, really want cryptography that is provably impossible to break. Unfortunately, we cannot have it, because asking this of modern-day computational complexity theory is a little bit like asking the ancient Greeks to solve the Delian problem. Still, we want to come as close as we can.

The classic flaw of capable people is overconfidence. It takes a certain arrogance to conflate “I do not see how to break this” with “This is unbreakable”, and such arrogance is remarkably common in otherwise smart people. Especially engineers. It is also deadly in this game. Any time you hear anyone — especially an “expert” — say that a cryptographic flaw can be ignored as “purely academic”, you should conclude they are the wrong kind of expert and run away.

More next time.