Turing Award; Google's First Crash

Turing Award 2016

The highest award in computer science, sometimes referred to as the Nobel prize of CS, is the Turing award. It is named for the English computer scientist Alan Turing, who was one of the key contributors to the codebreaking at Bletchley Park in the second world war and, in some ways, was the father of the first programmable computer, Colossus. This year the award went to Whitfield Diffie and Martin Hellman for the invention of public key cryptography. This is something that the Internet requires to function. Whenever you see "https" at the start of a URL, you are using some of their ideas. They published their work a long time ago, in 1976, and immediately prompted research into practical methods to implement their ideas.

Or as Hellman put it:

When a lock icon appears at the bottom of your browser, it's using public key cryptography. Your computer and the merchant's computer can talk back and forth across an insecure channel and exchange credit card information in a way that someone listening in cannot get it.

Before Diffie and Hellman, the big challenge in cryptography was key distribution. The sender (traditionally called Alice) and the receiver (Bob) couldn't just send the new key over the communication medium since it was assumed that the bad guy (traditionally called Eve, since she can eavesdrop) would see it, too. So if you were the federal government during the Cold War you would put the keys in a briefcase, padlock it to some guy's wrist, and then send him to the US embassy in Moscow. That was obviously slow and expensive. You can't really use a procedure like that when you want to buy a book on Amazon.

Diffie and Hellman came up with the basic idea of Alice and Bob agreeing on a key despite Eve listening to their entire conversation. This requires something that is relatively easy to do, but incredibly hard to undo, unless you have an extra piece of information. The Internet uses RSA (named for Rivest, Shamir, and Adelman, and also the founders of the company, RSA), where the easy thing is to multiply two numbers together and the hard thing is to factorize the resulting number. It turns out that mathematically it is possible to decide if a number is prime or not (called composite) without being able to factorize the number if it is composite. You might remember from high school math that factorization into primes is unique, in the sense that 21 is 3*7, but it is never also 2*11 or something. This is called the fundamental theorem of arithmetic and it is also why we don't consider 1 to be prime despite it seemingly passing the test of only being divisible by itself and 1. Because then, 21 would be 3*7, but also 3*7*1 and so would not be unique. Anyway, it turns out that factorizing a large number (200 digits, say) is really hard, although there is a potential loophole in Internet security since nobody has ever been able to prove it is hard and that there is no clever algorithm that could solve it fast. But for now, nobody has found an easy way to factorize and so Internet security remains...secure.

The best explanation of public key cryptography that I have ever seen is this video that shows how it works by mixing paint instead of multiplying large numbers. The second half of the video goes into all the modular arithmetic that is actually used in the Internet protocols.

Google Car Crash

It had to happen eventually and a few days ago it did. One of Google's self-driving cars had an accident where it was the self-driving car's fault. There have been many accidents before, but all were the fault of the other driver. Mostly they were rear ending the Google car since it drives very cautiously. In fact, in the early days the cars could get stuck at a 4-way stop since they would always let other people go first. Anyway, in Mountain View on February 14th the car tried to edge past a bus avoiding some sandbags. Both the human driver and the car's computers thought the bus would let it merge in, but the bus moved and the two vehicles collided. This was the first accident where the car was at fault after about 1.5 million miles of driving (which makes for better statistics than most human drivers can manage).