of Alice and Bob
Alice and Bob After-Dinner Speech
the Zurich Seminar,
April 1984, by
Good evening Ladies and Gentlemen.
There comes a time when people at
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, who have been dragged here
kicking and screaming. So I thought it would be a good idea if I
you an instant, graduate course in coding theory.
Coding theorists are concerned
with two things.
Firstly and most importantly they
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 then Alice and Bob.
Now there are hundreds of papers
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 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's 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
dealings with Bob are not brought to the attention of her husband.
So Bob is a subversive stockbroker
and Alice is a
But Alice has a number of serious
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.
interference is so bad that Alice and Bob can hardly hear each
other. So another of Alice's problems is DEALING WITH NOISE.
On top of that Alice and Bob have
enemies. One of their enemies is the Tax Authority. Another is the
This is a pity since their
favourite topics of
discussion are tax frauds and overthrowing the government.
These enemies have almost
They always listen in to telephone conversations between Alice and
Bob. So Alice also has the problem of ENSURING
And these enemies are very sneaky.
One of their
favourite 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 recognises Bob's voice.
But no. You see Alice has never
met Bob. She has
no idea what his voice sounds like. So IDENTIFICATION is another
of Alice's problems.
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. So she's got an
AUTHENTICATION problem too.
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
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 organise a coup d'etat, while at the same time
minimising the cost of the phone call.
A coding theorist is someone who
Alice is crazy.
The other thing coding theorists
with is information.
Nothing else is like information.
very peculiar stuff. It can both be created and destroyed. You can
steal it without removing it. You can often get some just by
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
parts called Source coding, channel coding and secrecy coding.
First I'll tell you about source
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 peels 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
"Yes, you see we’ve all worked
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 thru 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
quietly he whispered "477".
Hardly a murmur.
He looked at his tutor. "What's
"Try again" says the tutor.
So he does. "318" - same again,
thing, hardly a murmur.
"Something's wrong" he says.
"Well" says the tutor, it's like
It's not so much the joke as the way you tell it!"
There is a curious sequel to 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
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,
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"
But Bob hears "I XXve to tell u
"What's that again" says Bob.
"I have to tell you about Mike"
"Didn't get the last word Alice"
Bob, "Can you spell it out"
"Mike India Kilo Echo" says Alice.
"Got India Kilo Echo, What was the
word" says Bob.
"Can you spell that?"
"Mike India Kilo Echo" etc.
Actually there have been lots of
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
B for Mutton
A Muse of Fire
(zee) for yourself
Finally we come to Secrecy Coding,
Secrecy Coding is what Alice uses
to try to stop
the tax authorities and the secret police understanding her telephone
Now cryptographers are very
peculiar people. They
have very devious minds.
Sometimes they encrypt jokes.
call these "Covert Jokes". People who make them are
An intelligible joke in its raw
form is called the
Plainjoke, and after encryption is called the Cipherjoke or
Cipherjokes are intelligible of
course only after
Decryption, or as some people call it, after explanation.
There are three kinds of attack on
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
But most powerful of all is the
Attack where he gets to ask the Cryptolaffer to explain WHY the joke
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.
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 standardise 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 standardised.
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
So what they do is to make most of
standardised, and to concentrate the non-standardization into one
part called the key.
So far so good. But of course the
non-standardised part, must be nonstandard in only standardised 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 standardised nonstandard way in order to
standardise on the overall non-standardization.
I hope this makes the position
Many cipher 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 standardise on it.
Coding theory is not without its
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
It was sent on 1830 from Little
Bighorn by General
Consider the message:
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