John Gordon: The Alice and Bob After Dinner Speech

The Alice and Bob After Dinner Speech

given at the Zurich Seminar, April 1984,<br>by John<br>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<br>something more relaxing. A change of pace. A shift of style. To put aside<br>all that work stuff and think of something refreshingly different.

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

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

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

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

In papers written by American authors Bob is frequently selling stock to<br>speculators. From the number of stock market deals Bob is involved in we<br>infer that he is probably a stockbroker. However from his concern about<br>eavesdropping he is probably active in some subversive enterprise as well.<br>And from the number of times Alice tries to buy stock from him we infer she<br>is probably a speculator. Alice is also concerned that her financial<br>dealings with Bob are not brought to the attention of her husband. So Bob is<br>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<br>telephone or by electronic mail. In the country where they live the<br>telephone service is very expensive. And Alice and Bob are cheapskates. So<br>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<br>Alice and Bob can hardly hear each other. On top of that Alice and Bob have<br>very powerful enemies. One of their enemies is the Tax Authority. Another is<br>the Secret Police. This is a pity, since their favorite topics of discussion<br>are tax frauds and overthrowing the government.

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

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

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

Now most people in Alice's position would give up. Not Alice. She has<br>courage which can only be described as awesome. Against all odds, over a<br>noisy telephone line, tapped by the tax authorities and the secret police,<br>Alice will happily attempt, with someone she doesn't trust, whom she cannot<br>hear clearly, and who is probably someone else, to fiddle her tax returns<br>and to organize a coup d'etat, while at the same time minimizing the cost of<br>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<br>else is like information. Information is very peculiar stuff. It can both be<br>created and destroyed. You can steal it without removing it. You can often<br>get some just by guessing. Yet it can have great value. It can be bought and<br>sold.

One type of information is called Money.

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

Source, channel and secrecy coding

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

Source coding

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

There is a story about a...