The Alice and Bob After Dinner Speech
given at the Zurich Seminar, April 1984,
by John Gordon, by invitation of Professor James Massey

Good evening Ladies and Gentlemen.

There comes a time when people at a technical conference like this need something more relaxing. A change of pace. A shift of style. To put aside all that work stuff and think of something refreshingly different.

So let’s talk about coding theory. There are perhaps some of you here tonight who are not experts in coding theory, but rather have been dragged here kicking and screaming. So I thought it would be a good idea if I gave you a sort of instant, five minute graduate course in coding theory.

Coding theorists are concerned with two things. Firstly and most importantly they are concerned with the private lives of two people called Alice and Bob. In theory papers, whenever a coding theorist wants to describe a transaction between two parties he doesn’t call then A and B. No. For some longstanding traditional reason he calls them Alice and Bob.

Now there are hundreds of papers written about Alice and Bob. Over the years Alice and Bob have tried to defraud insurance companies, they’ve played poker for high stakes by mail, and they’ve exchanged secret messages over tapped telephones.

If we put together all the little details from here and there, snippets from lots of papers, we get a fascinating picture of their lives. This may be the first time a definitive biography of Alice and Bob has been given.

In papers written by American authors Bob is frequently selling stock to speculators. From the number of stock market deals Bob is involved in we infer that he is probably a stockbroker. However from his concern about eavesdropping he is probably active in some subversive enterprise as well. And from the number of times Alice tries to buy stock from him we infer she is probably a speculator. Alice is also concerned that her financial dealings with Bob are not brought to the attention of her husband. So Bob is a subversive stockbroker and Alice is a two-timing speculator.

But Alice has a number of serious problems. She and Bob only get to talk by telephone or by electronic mail. In the country where they live the telephone service is very expensive. And Alice and Bob are cheapskates. So the first thing Alice must do is MINIMIZE THE COST OF THE PHONE CALL.

The telephone is also very noisy. Often the interference is so bad that Alice and Bob can hardly hear each other. On top of that Alice and Bob have very powerful enemies. One of their enemies is the Tax Authority. Another is the Secret Police. This is a pity, since their favorite topics of discussion are tax frauds and overthrowing the government.

These enemies have almost unlimited resources. They always listen in to telephone conversations between Alice and Bob. And these enemies are very sneaky. One of their favorite tricks is to telephone Alice and pretend to be Bob.

Well, you think, so all Alice has to do is listen very carefully to be sure she recognizes Bob’s voice. But no. You see Alice has never met Bob. She has no idea what his voice sounds like.

So you see Alice has a whole bunch of problems to face. Oh yes, and there is one more thing I forgot so say - Alice doesn’t trust Bob. We don’t know why she doesn’t trust him, but at some time in the past there has been an incident.

Now most people in Alice’s position would give up. Not Alice. She has courage which can only be described as awesome. Against all odds, over a noisy telephone line, tapped by the tax authorities and the secret police, Alice will happily attempt, with someone she doesn’t trust, whom she cannot hear clearly, and who is probably someone else, to fiddle her tax returns and to organize a coup d’etat, while at the same time minimizing the cost of the phone call.

A coding theorist is someone who doesn’t think Alice is crazy.

Information
The other thing coding theorists are concerned with is information. Nothing else is like information. Information is very peculiar stuff. It can both be created and destroyed. You can steal it without removing it. You can often get some just by guessing. Yet it can have great value. It can be bought and sold.

One type of information is called Money.

There are people who refuse to concede that money can be created and destroyed. They spend their entire lives altering records and making adjustments to ensure that every time a bit of money leaves some place, an equal bit seems to appear somewhere else. These people are called accountants.

Source, channel and secrecy coding
Coding theory, like Gaul, is divided into three parts, called source coding, channel coding and secrecy coding.

Source coding
First I’ll tell you about source coding. Source coding is what Alice uses to save money on her telephone bills. It is usually used for data compression, in other words, to make messages shorter.

There is a story about a student of information theory on his first day at college. He had entered a strange, bizarre world. The only sounds were the occasional calling out of a number by one of the professors, followed by laughter. One professor would say ‘52′, there would be a short pause then peals of laughter. Someone else says ‘713′, same thing, everyone falls down laughing.

“What’s going on here?” he asked his tutor.

“We’re telling jokes,” said his tutor.

“Telling jokes?”

“Yes, you see, we’ve all worked here so long we know each other’s jokes. There are a thousand of them. So, being information theorists we applied data compression. We just assigned them all numbers, 0 through 999. It saves a lot of time and effort. Would you like to try? Just say any number 0 to 999…”

He wasn’t fully convinced. But he tried. Very quietly he whispered “477″.

Hardly a murmur.

He looked at his tutor. “What’s wrong?” he said. “Try again,” says the tutor.

So he does. “318″ - same again, not a thing, hardly a murmur.

“Something’s wrong,” he says.

“Well,” says the tutor, “it’s like this - it’s not so much the joke as the way you tell it!”

There is a curious sequel to this story. This student eventually succeeded by accident in the most dramatic and unexpected way. He called out a number outside the range 0 to 999. “Minus 105,” he said.

At first there was stunned amazement, then first one professor laughed, then another then another, till they were all rolling about holding their sides.

None of them had heard that one before.

Channel coding
Next we come to channel coding. Channel coding is what Alice uses to overcome the noise and interference on the line. Most people have a natural instinct for channel coding. What they do is to spell out important words. This adds redundancy and enables the listener to cross check. If part of the message is lost the missing bit can be reconstructed from the remaining part.

Many organizations such as the military, the aviation community, the Police and so on use a standard phonetic alphabet specially designed for this purpose. It goes Alpha, Bravo, Charlie, Delta, Echo, Foxtrot, etc. So one says “Mike” and “November”, which is much clearer than saying “M” and “N” which are easily confused otherwise.

Alice uses this to explain to Bob that her husband Michael is getting suspicious of her stock option dealing.

“I have to tell you about Mike,” she says. But Bob hears “I XXve to tell u XXt Xxike”.

“What’s that again?” says Bob. “I have to tell you about Mike,” says Alice.

“Didn’t get the last word Alice,” says Bob, “can you spell it out?”

“Mike India Kilo Echo” says Alice.

“Got India Kilo Echo, what was the first word?” says Bob.

“Mike”

“Can you spell that?”

“Mike India Kilo Echo” etc.

Actually there have been lots of other phonetic alphabets. The predecessor to the International Phonetic Alphabet went Able, Baker, Charlie…

Then there are those based on names of countries:- Africa, Brazil, Chile, Denmark, England, France, Greenland, Holland, India, Japan, Khazakistan, Lithuania, Morocco, Niger, Oman, Papua, Qatar, Russia, Spain, Tanzania, Uruguay, Venezuela, Westphalia, Yemen, Xanadu, Zambia.

My personal favorite is this:

A for ‘Orses
B for Mutton
C for Yourself
D for Mation
E for Brick
F for Vescence /* EFFERVESCENCE do you get it? do you get ALL of it? :)) -Luan */
G for Police
H for Consent
I for Lutin
J for Orange
K for Teria
L for Leather
M for Sis
N for Mation
O for A Muse of Fire
P for Ate
Q for A Song
S for Something Else
T for Two
U for Mism
V for La France
W for Mism
X for Breakfast
Y for Lover
Z (zee) for yourself

Secrecy coding
Finally we come to Secrecy Coding, or Cryptography. Secrecy Coding is what Alice uses to try to stop the tax authorities and the secret police understanding her telephone conversations.

Now cryptographers are very peculiar people. They have very devious minds. Sometimes they encrypt jokes. Security agencies call these “Covert Jokes”. People who make them are CryptoLaffers.

An intelligible joke in its raw form is called the Plainjoke, and after encryption is called the Cipherjoke or Cryptojoke. Cipherjokes are intelligible of course only after Decryption, or as some people call it, after explanation.

There are three kinds of attack on an unintelligible cryptojoke according to the Jokeanalyst’s resources. Firstly there is the Cipherjoke-only attack in which the Jokeanalyst is assumed to have unlimited amounts of material which is alleged to be funny.

Secondly and more powerfully there is the Known Plainjoke Attack in which he is given examples of jokes together with their explanations.

But most powerful of all is the Chosen Plainjoke Attack where he gets to ask the Cryptolaffer to explain WHY the joke is funny.

Feeble jokes are usually encrypted using only a very simple cipher, like changing the punch line. This is called the DEFLECTED ENDING SYSTEM or DES.

Very good jokes, the comprehension of which by outsiders could constitute a threat to national security, are encrypted much more securely, usually by completely changing the scenario, the plot and the conclusion. This is the PARTICULARLY KLEVER COVERUP or PKC. The best known PKC RESISTS SERIOUS ATTACK and is therefore called the RSA.

As a corollary of course, it follows that only very gifted, intelligent people can truly appreciate a funny speech.

Standardisation
Since it is difficult to design a good cipher, and since the apparatus is very expensive, a lot of work has been done recently to try to standardize on them. Even as I speak the International Standards Organization is meeting to decide on this very issue. Since there is a lot of confusion on this point I have been asked to make the position clear. The purpose of language is to convey information. This only works if both sender and receiver of information both use the same system. In other words language only works precisely because it is standardized.

The purpose of cryptography on the other hand is to make the message unintelligible except to one person. In other words cryptography only works precisely because it is NOT standardized.So what they do is to make most of the cipher standardized, and to concentrate the non-standardization into one part called the key.

So far so good. But of course the key, the non-standardized part, must be nonstandard in only standardized ways. And also key management must conform to certain standards. In other words standards are being formulated whereby the nonstandard parts, which must conform to certain standards of non-standardization, are also to be handled only in a standardized nonstandard way in order to standardize on the overall non-standardization.

I hope this makes the position clear.

Weak keys
Many ciphers have certain bad keys. If you use one of them the cipher is easily broken. For instance all-zeros is a weak key for the DES. There has been a lot of research done into searching for weak keys. Over the years more and more weak keys have been found till now one has to be quite careful to avoid them.

Perhaps it would be a better idea if we looked for strong keys. In fact, why not look for THE STRONGEST POSSIBLE KEY.

Then we could all standardize on it.

Processing delay
Coding theory is not without its problems. The introduction of source coding, channel coding and secrecy coding often introduces something called PROCESSING DELAY. This is the delay caused by the time it takes to do all this coding and decoding. These delays can be enormous.

History gives us instances when this delay has changed the course of world events. There is a recorded case of a two-word military signal which suffered a processing delay of 150 years. The message, deciphered at the Pentagon in 1972, simply read “Send Reinforcements”. It was sent on 1830 from Little Bighorn by General Custer.

Consider the message: “Return home at once, trip cancelled.” and think of the effect on world events if it had been decoded in time. It was sent in 1492 by Isobella of Spain to Christopher Columbus.

But these delays are nothing in comparison with the next example. We are told by Suetonius that Julius Caesar communicated with the Orator Cicero in a cipher in which ‘A’ was sent as ‘B’, ‘B’ as ‘C’ and so on. If you apply this cipher to HAL - the computer in the Stanley Kubrick movie: 2001 - you get IBM. Some correspondence from Julius Caesar to Cicero in this complex cipher have finally been deciphered by GCHQ and will be published in the June edition of Cryptologia. Their contents paint a disturbingly different picture of the world from Caesar’s official dispatches to Rome in De Bello Gallico.

I am privileged to have an advance copy, from which I will read you an extract.

“Alexandria, April 14th 48 BC (think about it)

Dear Marcus Tullius

Thank the Gods you and I have a secure cipher. I would not care to have our messages read by my enemies. Frankly I don’t trust most of the Senate.

Take Mark Anthony. Would you trust him? He’s so incompetent he couldn’t organize a libation at an orgy.

Take Gaius Brutus. Would you buy a used chariot from this man? I think he’s plotting behind my back. Sometimes he scares the toga off me.

And as for the Gauls. What a bunch of morons. I thought all their problems would be solved when we formed the GEC -the Gallic Economic Community. But what happens? We guarantee minimum prices on food exports, the so called “Green Denarius”. We provide subsidies on cheap labor saving gadgets - like slaves. Then what happens? We get a run on the Denarius. Inflation runs at record levels. And they squander our subsidies on gross overproduction of wine. We have to sell it off cheap to the Barbarians to maintain the price level within the GEC.

I’m fed up with the whole business. When I get back to Rome I’ll retire. I have it all planned. I lied about the size of Gaul in my official dispatches. I’ve found the most divine little spot for my retirement which I’m keeping quiet about. I’m not having those Senators getting their grubby hands on it. And I’ve taken steps to make sure they never can. So for your ears alone Marcus Tullius, I have my special, secret retirement place all organized. It doesn’t appear on any map because I authorize the maps.

Officially it doesn’t exist. So it can’t be found or taxed. I’ve managed to conceal a whole extra part of Gaul!

So forget De Bello Gallico. The reality is Gaul is divided into FOUR parts.”

The modern world
Well that ends the instant course on coding theory. I would like to finish with a few words on the impact that information technology is having on our everyday lives.

Science has marched ahead so fast that we take for granted the most incredible technological developments. Magnetrons, which were a closely guarded secret during the 1939-45 war are now part of every microwave cooker. And made in Japan. When I was a child, space travel was science fiction. Yet today, advance is so rapid that even the astronauts who set foot on the moon in 1969 had never seen a digital watch. Nor a pocket calculator.

Pocket calculators! Now there’s something. They’re so complicated! I have a calculator which has sines, cosines, tangents, logarithms, hyperbolic functions and multiple nested parentheses. You can program it in Fortran, Algol, Basic, Pascal, Forth, Fifth and Sixth, ADA and Carruthers. It will factorize primes for you. At present it’s working on the Halting Problem.

It translates from one language to another. From German to Spanish. From Macedonian to Esperanto. From Cantonese to Greek. Or from American to English.

It is, in fact, a multiprocessor system. There are 22 Transputers in there. Sometimes they organize a game of football between them.

It has a full color, wraparound wide screen, liquid crystal, three-dimensional holographic display. It’s called HoloChromaCinePhotoRamaScope.

Its audio facilities include Dolby Digital Decaphonic surround sound. On the way here I watched “The Labyrinth” on it.

It also has synthetic speech and a voice recognition system. I often talk to it. I tell it my problems. Sometimes it psychoanalyses me. It has me figured as paranoid. But that’s just because it keeps getting at me. But don’t get me wrong - it can be very user friendly. In fact you can program precisely HOW user friendly you want it is to be on a scale from ONE to TEN.

On a setting of ONE it won’t even interrupt a football game to answer you. But on a setting of TEN it’s so friendly that on a cold day it pre-heats its pushbuttons.

But no matter who smart it SEEMS, deep down inside it’s just a dumb old computer.

One time I got really mad at it. Like all computers, it knew precisely what I wanted it to do. It knew exactly what I MEANT. So why does it have to go and DO what I SAID?

How do you get even with a dumb machine like that?

First I tried slapping it around a little. I pushed its buttons a bit hard. I threatened it. “How would you like a busted display” I said.

But it did no good. It just said “I am virtually unbreakable - and I’m not going to take any notice till you enter the data nicely, like you used to do.”

Whatever I did it always seemed to win.

I decided to have a man-to-man talk with it. So I sat it down and said to it “Who’s the boss here, you or me?”

No reply.

Again I ask “Who’s the boss, you or me? Go on, answer me!”

“I’m thinking, I’m thinking,” it said.

So I hit it. Hard. Too hard. I cracked its case.

At first I thought that was the limit of the damage. But then little things started to go wrong. At first there was nothing definite. Nothing you could put your finger on. Just little things like stuttering. It just didn’t sound quite the same. Its voice seemed to lack its former confidence.

Then once I caught it making an arithmetic mistake. Of course I didn’t mention it. But you could tell it knew. Its self image was shot to pieces.

Saddest of all, it forgot our anniversary - of the day I bought it. In the past this had been a special time for us.

I just couldn’t bear it any longer. One evening I tucked it up snugly in its case, lit candles, played a record which was popular when we first met, and sat down beside it.

“Where did we go wrong?” I said. But it had it pride. It wasn’t about to weaken in front of a non-machine.

“Wrong? Nothing is wrong,” it said. “Just insufficient data.”

But underneath you could tell it was hurt.

From there it was a rapid downhill slide.

Now it just mutters to itself. It can only do very simple calculations on small numbers.

Finally came the ultimate indignity. It lost control. It leaked electrolyte all over its case.

I felt so bad about it. My other gadgets weren’t happy about it either. They all came out in sympathy for the calculator. My watch gave me a bad time. My power tools keep blowing fuses.

Then one night last week I was driving my car back from London when suddenly the engine stopped all by itself on this lonely country road.

I tried to get out but the solenoids were inhibited by the central locking computer. Suddenly the air conditioner came on and started to blow out freezing cold air. It made a noise like wind whistling through the trees. Then this creepy music came from the loudspeaker. The sort of music they play in movies when the hero is lost in a dark forest.

I got scared. The cold, the wind and the weird music got to me. Then it started to speak.

“You’re the guy who beats up pocket calculators!”