1.1 Cryptography in a Nutshell

1.1.1 The problem

Cryptography is the study of building secure systems in the presence of adversaries. The setting is easy to describe: Alice wants to send Bob a message over a network that an attacker (conventionally named Eve) can observe, and possibly modify. The network itself offers no protection; the only thing Alice and Bob may assume they possess is a shared secret key $k$, unknown to Eve.

Once such a key exists, two properties become the baseline goal:

• Confidentiality. Eve, who sees the traffic, cannot figure out what messages Alice and Bob are exchanging.
• Integrity. Eve cannot tamper with the traffic without the tampering being detected.

Confidentiality alone is not enough. A scheme that hides the content but lets an attacker rearrange or flip bits in transit can deliver to Bob a message that Alice never wrote. Modern encryption schemes therefore provide both properties at once.

The same two properties govern a setting that looks nothing like a network: files encrypted on disk. Tools such as EFS and TrueCrypt store ciphertext in place of plaintext, so that a stolen disk leaks nothing, and so that a file whose stored bits have been edited is recognized as damaged when it is read back. Philosophically the two settings are one, because the writer and the reader are the same person at two different times: today’s Alice sends a message to tomorrow’s Alice, the disk stands in for the network, and whoever walks off with the machine plays the eavesdropper. Everything the network asks of a cipher, storage asks as well.

Before either property can be discussed, Alice and Bob must actually have a shared key. The task of getting two parties who have never met to agree on a secret key over an insecure channel (key establishment) is the other half of cryptography. This is why the whole subject has two parts:

Secure key establishment, and secure communication once a shared key exists.

The first part of this tutorial takes the shared key as given and asks how to use it; the second part shows how two parties can agree on one over a channel an attacker controls.

1.1.2 Symmetric encryption, abstracted

A cipher is a pair of matching procedures: one scrambles a message under a secret key, and the other undoes the scrambling with the same key. The algorithms may be public; the key is the part Alice and Bob share and Eve does not. To send a message $m$, Alice computes $c:=E(k,m)$ and transmits $c$; Bob recovers $m:=D(k,c)$. The cipher is symmetric because both parties use the same key $k$. Later we will meet public-key ciphers, where the encryption and decryption keys are different; that is the second half of this tutorial.

How the key is spent matters as much as what it protects. A single-use key encrypts exactly one message, as when a fresh key is generated for every encrypted email. A multi-use key encrypts many: the file system above seals all of a disk’s files under the same key. The definition of a cipher promises nothing about reuse, since $E$ and $D$ say only what happens for one fixed $k$ and one message; a key that guards many messages needs machinery around the cipher, and building that machinery is much of the work ahead.

A cipher by itself says nothing about what security means. Writing down $(E,D)$ is easy; arguing that $E$ actually protects $m$ against a specific class of attacks is the mathematical content. That is the discipline to which we turn in earnest in Chapter 2.

1.1.3 Cryptography does much more

Encryption is only the visible tip of the subject. Four families of applications recur throughout this tutorial, and each one looks impossible until the construction is in view.

Digital signatures. A signature is the analog of a handwritten signature, and the physical model breaks immediately in the digital world: a handwritten mark is a fixed image, so an attacker who obtains one signed document can cut and paste that image onto a different document. A digital signature therefore cannot be a fixed string that the signer attaches to everything. The resolution is that a secure signature must be a function of the message being signed: pasting it to new content invalidates it. Construction and proofs come later in this tutorial.

Anonymous communication. Alice wants to talk to a chat server Bob without revealing who she is, and cryptography can do it in both directions: Bob answers Alice although he has no idea whom he is answering. The standard mechanism is a mixnet, a sequence of proxies through which messages are layered and peeled off with encryption, so that no proxy learns who is talking to whom. Anonymity in turn supports stronger mechanisms, such as anonymous digital cash: Alice spends a digital coin at an online merchant without the merchant learning her identity, exactly as physical cash works today. But digital money has an obvious flaw: Alice can copy the coin before spending it. Anonymity is then in tension with security: if a coin leaves no trace, who stops the double spender? The trick that resolves the tension is asymmetric: spend the coin once and your identity stays hidden; spend it twice and the two spendings together reveal who you are. Anonymity is granted to honest users and withdrawn at the moment of fraud.

Secure multi-party computation (MPC). Consider an election: voters submit votes to a center, which must compute the majority while revealing nothing about any individual vote. Or a private auction (a Vickrey auction, where the highest bidder wins but pays the second-highest bid): the participants want to learn the winner and the price, and nothing about the losing bids. Both are instances of a general problem: parties hold private inputs $x_1,\dots ,x_n$ and want to compute a function $f(x_1,\dots ,x_n)$ so that the value of $f$ becomes public and nothing else is revealed. The obvious solution hands every input to a trusted authority who computes $f$ and keeps the inputs secret, but it builds the system around a party everyone must trust. The central theorem of MPC says that authority is unnecessary:

Theorem (secure function evaluation, informally)

Any functionality that can be computed with the help of a trusted authority can also be computed without one, by a protocol among the parties themselves, leaking nothing beyond the output.

The parties talk to each other over the network, and at the end $f$ is known to everyone while each individual input remains private. The construction is far from trivial and appears near the end of this tutorial.

Magical applications. Two more constructions have no classical counterpart at all.

• Privately outsourcing computation. Alice sends an encryption of her search query to Google; the encryption scheme has the property that Google can run its search algorithm directly on the encrypted values, obtain an encrypted result, and send it back, all without ever seeing the plaintext. (Such schemes are called fully homomorphic. They are a recent development, and running a full search on encrypted data would take an absurdly long time today, but the fact that it can be done at all is remarkable.)
• Zero-knowledge proofs. Alice publishes a number $N=p\cdot q$, the product of two primes of a thousand digits each. Factoring $N$ is believed infeasible, so Bob, who sees only $N$, cannot possibly reconstruct $p$ and $q$. Yet Alice can run a protocol that convinces Bob that she knows the factorization while leaking nothing about what $p$ and $q$ actually are, and this is a theorem, not folklore. The phenomenon generalizes: essentially every statement that has a proof has a zero-knowledge proof, so one can prove that one has solved a sūdoku puzzle without revealing a single cell of the solution.

A common thread runs through all of the above: cryptography makes seemingly impossible tasks possible, in the sense of trusting without a trusted party, proving without revealing, and computing without seeing.

1.1.4 The method: three steps

A primitive is the standard name for a basic building block of cryptography. Every primitive in this tutorial (encryption, signatures, message integrity, key exchange) follows the same template, and the pattern will recur in every chapter:

1. Specify the threat model precisely. What does the attacker control? Can she only observe ciphertexts, or can she obtain encryptions of messages of her choice? What is her goal (recovering the key, recovering one bit of a specific message, forging one signature on one chosen message)? A security claim without a threat model is meaningless, because the answer changes with the model.
2. Propose a construction. A concrete algorithm pair, built from published, peer-reviewed components.
3. Prove a security theorem. “If an attacker can break this construction under the stated threat model, then there exists an algorithm that solves problem $X$ efficiently,” where $X$ is a problem the community believes to be hard (factoring, discrete logarithm, or an assumption about pseudorandomness). The proof is a reduction: the attacker is plugged in as a subroutine that breaks $X$. Since we do not think $X$ is breakable, the attacker cannot exist.

The caution is not pedantic. History (Section 1.2) is a catalog of ciphers that sounded convincing and fell, because no one had said in advance what “secure” was supposed to mean.

1.1.5 What cryptography is not

The overview closes with three warnings worth keeping in mind:

• Cryptography is not the solution to all security problems. It protects data in transit and at rest; it does not fix software bugs, and it does not stop someone from being fooled by social engineering. It is a tremendous tool, and one that is routinely misused.
• A cryptosystem is not reliable unless implemented and used properly. WEP, the old standard for encrypting Wi-Fi traffic, contains many mistakes in how it uses cryptography; it is the standard example of how not to do things.
• You should not invent your own cipher. There are endless examples of ad-hoc designs that looked clever and fell to professional cryptanalysis within months. Use published, standardized algorithms (AES, SHA-2, TLS), reviewed by thousands of people whose job is to break them.

The history comes next, because the historical ciphers are where the need for a threat model first becomes visible.