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.

The composition of subsystems in quantum theory is defined in terms of a mathematical operation known as the tensor product. We proceed to explain this concept, and to show how it fits in the Hilbert space calculus.

The propagation method can be used to describe a particle with wave character moving in an arbitrary one-dimensional potential, $V(x)$. This is done by approximating the potential as a series of potential steps. For a particle of energy $E$ incident from the left, transmission and reflection at the first step is calculated along with phase accumulated propagating to the step and expressed as a $2\times 2$ matrix.

The introduction of the Hilbert space as the essential mathematical structure for the formulation of quantum theory was motivated by the following facts.

In Chapter 2, we saw that the nascent quantum theory was divided between two different descriptions of time evolution.