We introduce the task of key distribution, whose goal is to allow two mutually trusting users, Alice and Bob, to generate a random shared key that is unknown to any eavesdropper in the protocol. We start by precisely defining this task and our model for adversaries. We then show how to realize it in a simple toy scenario, which will help us demonstrate the key ideas. Finally we introduce information reconciliation, which is an important building block in the protocols that we will study in subsequent chapters.

In this chapter we introduce a variant of the BB’84 quantum key distribution protocol, the E’91 protocol due to Ekert. We show that this protocol achieves a higher level of security called “device independent security.” What this means, informally, is that the new protocol’s security doesn’t rely on Alice and Bob performing trusted measurements on their qubit in each round. We sketch the proof of security of the E’91 protocol, which rests on the property of entanglement monogamy.

In this chapter we present an alternative path to base security in challenging settings. We will discover that physical assumptions on the adversary, such that they have a bounded or a noisy quantum memory, can be leveraged to design secure protocols for tasks, such as 1-2 oblivious transfer, for which there cannot exist an unconditionally secure protocol. To prove security we make a fresh use of uncertainty relations introduced earlier in the context of quantum key distribution.

One of the first applications of quantum information to cryptography to be discovered is to the creation of money that cannot be copied. Due to the no-cloning principle, which states that there is no procedure that can copy an arbitrary quantum state, we can hope to create perfectly secure money based on quantum information. In this chapter we study how this can be done by following Wiesner’s idea from the 1970s. To analyze the security of Wiesner’s scheme we develop a formalism for general quantum attacks by studying quantum channels, and encounter some limitations of Wiesner’s scheme.

This chapter introduces the basic mathematical formalism for working with quantum information. We discover qubits, or quantum bits, how to combine them using the tensor product, and how to measure them by choosing a basis. We discuss unitary operations, which are elementary transformations on qubits. The chapter ends with a convenient representation of qubits as vectors on the 3-dimensional Bloch sphere, and a useful “cheat sheet,” which summarizes useful definitions and identities.

Delegated computation is a two-party task where there is a large asymmetry between the two parties: on the one hand, Alice would like to execute a quantum computation, but she does not have a powerful enough quantum computer to execute it. On the other hand, Bob has a quantum computer, but he is not trusted by Alice. Can Alice make sure that Bob executes her computation correctly for her? In this chapter we present three very different approaches to this problem. Each of the approaches is based on a different model for quantum computation, and the chapter also serves as an introduction to these models.

A quantum key distribution (QKD) protocol allows two honest users Alice and Bob to harness the advantages of quantum information processing to generate a shared secret key. The most well-known, and indeed the first QKD protocol that was discovered, is called BB’84, after its inventors Bennett and Brassard and the year in which their paper describing the protocol was published. In this chapter we describe the BB’84 protocol and we introduce the main ideas for showing that the protocol is secure.

In this chapter we consider the problem of amplifying secrecy, or uncertainty. This is the problem of privacy amplification: given a partially secret string, how do we make it almost-perfectly secret? This task forms one of the key building blocks in the protocol for quantum key distribution that we develop in later chapters. It can be solved using a fundamental object from the theory of pseudorandomness called a randomness extractor. We introduce an extractor based on hashing and show that it can be used to perform privacy amplification.

Quantum information provides an advantage for cryptographic tasks in a wide variety of settings. In this chapter we focus on applications involving two parties and look beyond key distribution for other tasks where quantum information can play a role. This includes coin flipping, oblivious transfer, and other primitives in two-party cryptography.

“We revisit the quantum one-time pad and investigate the possibility of shortening the key used for quantum encryption. We first provide an impossibility result, and then show how it can be circumvented in two different ways: using approximate encryption, and by opening the door to the fascinating world of computational security. We also discuss a new possibility for quantum encryption, which is known as certified deletion: this is the possibility for the encrypter of a secret to request that the ciphertext is provably and irrevocably erased.”

Entanglement is one of the most fundamental, and intriguing, properties of quantum mechanics. It is also at the heart of quantum cryptography! In this chapter we start by giving a clear mathematical definition of entanglement. We give two classic applications, to superdense coding and to secret sharing. We then investigate two complementary properties of entanglement that we will use deeply in cryptographic applications. The first is nonlocality, which we investigate through the famous CHSH game. The second is the monogamy of entanglement, which we demonstrate using a three-player version of the CHSH game.

We study our first cryptographic tasks: secure encryption of a quantum state. We describe the classical one-time pad and present its quantum extension, the quantum one-time pad, which achieves perfectly secure quantum encryption. Before studying this task, we extend the mathematical formalism introduced in Chapter 1 by studying density matrices, general measurements on quantum states, and the partial trace operation.

How do we define knowledge, and, crucially for cryptography, ignorance? In this chapter we lay the basis for future security proofs by formalizing the notion of knowledge of a quantum party, such as the memory of an eavesdropper, about a classical piece of information, such as a secret key. For this we introduce an appropriate measure of conditional entropy, the min-entropy, and introduce important tools to bound it using guessing games.