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.

Leave a Reply