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:

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:

$$\sqrt{\sqrt{2*\sqrt{\sqrt{2*\sqrt{\sqrt{2*\frac{96389}{76504}}}}}}}$$

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.

Cryptography Part 1: Drunken rambling introduction

There is a series of posts forming in my head. I have no unifying theme nor particular audience in mind, so they will be even more rambling and incoherent than usual. Also I plan to have a drink or two before each just to complete the effect. You have been warned.

Let’s play a little game. You and I will be on the same team for a change. This is our asset:

It has 16-64 GB of storage, consumes 0.5 watts, and occupies 11.25 square inches.

On the bright side, we do have two of them. One each.

This is our adversary:

It has 3-12 exabytes of storage, consumes 65 megawatts, and occupies 100000 square feet. Also, it is operated by people smarter than you, smarter than me, and smarter than anybody either one of us has ever heard of.

The game is this. You and I will try to have a conversation over a great distance that is unintelligible to this adversary.

Now, perhaps it is just me — I still get excited by powered flight — but I find it awe inspiring that it might actually be possible for us to win. Not easily and not with certainty, but still.

That is what this series will be about. More or less.

Our story begins around 400 B.C. on the Greek island of Delos. Its citizens were suffering from internal strife threatening to tear the society apart. Or something. The island’s leaders consulted the Oracle at Delphi, who explained that Apollo was angry, and to appease him, the citizens had to construct a new altar double the size of their existing one.

Now, the ancient Greeks had far more rigorous minds than your typical modern engineer. To them, “construct” meant something very particular: Create something perfect using idealized versions of various masonry/carpentry tools. Extra credit for using only straightedge and compass.

(If you have never seen this game before, here are the rules. Given two points, you may use the straightedge to connect the points with a perfect line and extend it as far as you like. You may also set the compass to the distance between any two points, then draw a perfect circle with that radius centered on any other point. By starting with a few provided points and applying the straightedge and compass repeatedly, you generate new points at the intersections of all the lines and circles. That’s it. The ancient Greeks loved this stuff.)

Now, the altar to Apollo was a perfect cube. So the Delians started with a line segment AB having the same length as a side of the cube. Then they used a compass to draw a circle through A centered at B. Then they used the straightedge to extend AB to intersect the circle at C:

Since AC is twice AB, the Delians simply used that as the side of a new cubical altar.

But their problems only got worse. Eventually, they went back and asked the Oracle what was wrong. The Oracle explained that they had angered Apollo further by not following instructions, since they had created an altar not two times but eight times the original’s volume. Apparently, gods can be picky.

The Greeks eventually solved this problem by adding various interesting contraptions to their idealized toolkit. But the extra credit problem remained: Given a segment of length 1, can you construct one of length $$\sqrt[3]{2}$$ using only straightedge and compass?

This problem stumped geometers and would-be geometers for several years. Two thousand, actually. That is how long humanity needed to develop the mathematical tools to solve this Delian problem, as it came to be known. What that solution was and how it relates to anything will be the topic for…

Next time: Gauss, Galois, et. al.

(I did try to warn you.)

Au revoir, Bond Girl

I have lost my co-blogger.

Over the next few days, I will be removing her posts from this blog. I have already removed her contact information from the sidebar.

Q: “Why?”

A: Because she asked me to.

Q: “Why did she do that?”

A: I will not answer. I am not going to release any of our private correspondence, and I am certainly not going to put words in her mouth. So, seriously, don’t ask.

For my part, I am sorry to see her go. I have the deepest respect and appreciation for her on both a personal and a… whatever-co-blogging-is-al… level. She single-handedly increased my readership by a factor of #DIV/0!. Speaking of which, you should all unsubscribe now.

I honestly believe her decision was dictated by her conscience and her reason, just as my actions are dictated by mine.

I would welcome her back any time.

I will leave her posts up for a few days so readers can save copies of their favorites. Her self-evident.org Email address will continue to work until she asks me to shut it down.

The NSA revelations finally got interesting

Time to pay attention. (related video)

Quick background on my perspective: Stories about Snowden himself are boring. Stories about his girlfriend, stories about his politics, and even speculations about his being an agent of Russian intelligence… Boring.

More interesting are the revelations themselves, painting an NSA whose general goal appears to be the interception and permanent storage of all human communication. Everywhere.

But how are they doing it? By obtaining covert access to Google’s servers? By convincing Microsoft to change Skype’s protocol from peer-to-peer to peer-to-Microsoft? By forcing Web site operators to hand over their SSL keys?

How pedestrian. I mean, this is the agency created as a direct response to the Allied experience during World War II, where without the code breakers, we might have lost. This is the quasi-military organization absorbing billions of dollars per year while remaining “non-existent” for decades.

Speculating about NSA’s capabilities, especially cryptological capabilities, has been a hobby horse of mine for a long time. But none of the Snowden revelations shed any light whatsoever. Fair enough, I figured. Maybe NSA reserves the serious codebreaking for more important things than reading my Email. Maybe the good stuff was above his pay grade.

…or then again, maybe not.

N.S.A. Able to Foil Basic Safeguards of Privacy on Web

This is a jaw-dropping article. I am mildly paranoid, but things even I would have called dumb conspiracy theories are being reported as fact in the New York Times. (Ideas like NSA blackmailing Congress are still dumb, but even that I have been forced to upgrade from “laughable” to “very unlikely”.)

Let’s start with DNI Clapper’s response:

The fact that NSA’s mission includes deciphering enciphered communications is not a secret, and is not news

Compare that to the three essential claims in the NYT article:

1. NSA has practical attacks against SSL/TLS.
2. NSA has convinced / paid / forced U.S. manufacturers to insert deliberate vulnerabilities into both hardware and software security products.
3. NSA has infiltrated and undermined Internet standardization bodies, encouraging widespread adoption of vulnerable algorithms and protocols.

With due respect to Gen. Clapper, all of this is most definitely news.

I have a lot more to say, including my own wild-eyed speculations about (1). But I think I will make this multiple posts.

I will mention that (3) has touched off a bit of a firestorm among academic and professional cryptographers. If NIST cannot be trusted, we have a problem… And NIST can no longer be trusted.

Story of the week, if not the year.

P.S. The NYT graphic and (redacted) raw documents deserve close scrutiny.

Bitcoin pieces

It has been a volatile month for the world’s most popular experimental currency:

As you can see(1), the U.S. dollar — measured in milli-bitcoins — has been highly unstable. In Felix Salmon’s words:

[The dollar] is clearly not an effective store of wealth — just look at how quickly that wealth can be evaporated. Neither is it a useful payments mechanism, given how fast its value can fluctuate.

I might be paraphrasing slightly.

Ryan Avent makes the same point more verbosely (and politely).

More recently, Izabella Kaminska accuses me of accusing her of… You know what? Never mind. For the 0 of you who care, listen to the audio, read the comments, and judge for yourself. I will make two quick points:

1. With the possible exception of “shock jocks”, no journalist publicly expresses opinions significantly divergent from those of her sources or those of her organization, ever. This is not a conspiracy theory; it is common sense.
2. Anyone who accuses me of “the skin in the game fallacy” is a moron.

Ahh, that feels better.

[Update, following evening]

In my apparently excessive free time, I had a little back-and-forth with Izabella today. Note that I made this post last night, well before today’s exchange, but if you read them in the opposite order it looks even more like I am attacking her in particular.

For what it is worth, that was not my intention. It’s just that all of the Bitcoin bashing from the FT seems to have her name attached to it.

To rephrase my earlier assertion: Journalists have no more license to express their true opinions in public than I do to express mine to my employer. The eagerness of mainstream financial journalism to run Bitcoin bashing articles — no matter how idiotic — does say something about the financial sector’s reaction to Bitcoin, in my view. I consider this obvious.

But I do regret making it personal.

My next post will be purely technical.

(1) I know, my gnuplot-fu is weak. But it serves the purpose.