CH09_photon-QKD.tex

\chapter{BB84: Single-photon QKD}
\label{sec:9_bb84}

This chapter introduces single-photon quantum key distribution (QKD), specifically the first single-photon QKD protocol known as BB84, named for Charles Bennett and Giles Brassard, who developed it in 1984. First, to place the use of QKD in context, we provide a three-phase framework for secure communication. Second, we discuss the types of cryptosystems and the distinction between public key and symmetric key systems. We then present the basic idea of the protocol and the eavesdropper detection mechanism before introducing some of the early QKD testbed networks.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Three phases of cryptographically secure communication}
\label{sec:crypto-phases}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Secure communication using encryption proceeds roughly in the following three phases: first, the parties \textbf{\emph{authenticate}} each other, meaning that they prove they really are who they say they are and not somebody else.
Second, they select or \textbf{\emph{generate a key}} that they will use for encoding their messages. 
Third, they \textbf{\emph{encode}} their messages and encrypt their data, then send them to the other party where they will be decrypted -- the actual bulk data transfer phase of the conversation.

Authentication between Alice and Bob usually begins in the following way.
Alice begins by saying ``I'm Alice'' to Bob.
Bob replies with ``Okay, you're Alice, I'm Bob''.
The problem that both Alice and Bob face now is that anybody could have sent those messages.

Generally, the procedure two parties use to authenticate each other depends on one of three things\footnote{This applies in the real world as well; trying to get into a private club or a 1920s U.S. speakeasy might involve personal recognition, a physical token such as an actual key, or a password you have been given by someone else.}:
\begin{itemize}
    \item something you \textbf{\emph{are}},
    \item something you \textbf{\emph{have}},
    \item something you \textbf{\emph{know}}.
\end{itemize}
In particular the last one is quite important, because you know that the party that you are trying to communicate knows something, for example a secret pre-shared between the two parties, or generally and flexibly the private key corresponding to a particular public key that can be used as an authentication mechanism.

After authentication, Alice and Bob have to generate a \textbf{\emph{cryptographic key}}\index{cryptographic key} (or just ``key'').
There are many different ways to exchange keys, such as Diffie-Hellman key exchange, which we will not go into here.
The key will be used for encrypting the message.
One problem with the key is that once it is generated, it cannot be used forever.
It has to be changed at regular intervals in order to ensure that the encrypted data remains secure.

Once the key is generated, Alice encrypts her message with the key.
She sends it to Bob, where he will use his share of the generated key to decrypt the message and read it. 
Typically, this \textbf{\emph{bulk data encryption}}\index{bulk data enxryption} phase of the conversation uses a \textbf{\emph{symmetric key cryptosystem}}\index{symmetric key cryptosystem}, where Alice and Bob use the same key to encrypt and decrypt the messages.
Common forms include the now-outdated Data Encryption Standard (DES), the stronger (and still in use) 3-DES, and the modern Advanced Encryption Standard (AES)\index{Advanced Encryption Standard (AES)}. Less common is one-time pad (OTP)\index{one-time pad (OTP)}.
Later we will describe the one-time pad, which is also known as the \textbf{\emph{Vernam cipher}}\index{Vernam cipher}.

Quantum key distribution, or QKD, is used in the second phase of this process. 
Before we go into QKD, let's look briefly at how keys are established today when you use the Internet.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Key agreement and use}
\label{sec:key_agreement_use}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We have two parties, Alice and Bob, who are trying to communicate over a public channel.
``Public'' means that anybody has access to this channel, so any message that they transmit can be heard and intercepted by any other party.
This channel is therefore not secure.
And yet, Alice and Bob need to somehow authenticate each other, and prepare the key to be used for the bulk data encryption.

The simplest method is via a \textbf{\emph{pre-shared key (PSK)}}\index{pre-shared key (PSK)}.
Alice and Bob meet somewhere, face to face, long before they want to communicate. 
At this meeting, they create a shared secret between them, known to no one else. 
This key can then be used later to authenticate each other, and to help generate the keys used for the bulk encryption. 
Of course, for this method to work as a general mechanism for any two parties, every person must meet every other person. 
That requires $O(N^2)$ meetings for $N$ people, which is clearly not practical.

To compensate for this shortcoming, instead we use mechanisms that do not require this pairwise prior agreement.
One method is known as \textbf{\emph{public key cryptography}}\index{public key cryptography}.
Alice generates two keys, one is known as the ``public key'' and the other one is known as the ``private key''. 
They are a mathematically related pair.
The public key is used to encrypt the message, but it cannot be used to decrypt the message. 
The private key is needed to decrypt the message.
For this reason, public key cryptography is sometimes called \textbf{\emph{asymmetric encryption}}\index{asymmetric encryption}.
Bob's public key is published in some fashion that allows Alice both to find Bob's key when she needs it, and trust that it is really Bob's key.
Alice uses that to encrypt her message, and then sends it to Bob.
Bob then uses the private key (which he has kept secret) to decrypt Alice's message and read it.
The most prominent form of public key cryptography is known as RSA, designed by Rivest, Shamir and Adelman.

This process works, but it has some disadvantages.
It is slow and computationally expensive.
While it is theoretically possible for Alice to encrypt her actual message to Bob using public-key cryptography, which would combine the functions of authentication and encryption while eliminating the need for a separate key, it is not practical. 
AES, on the other hand, is easier to compute.
Therefore, we usually use \textbf{\emph{three separate functions}} as described in the last section, with RSA for authentication, Diffie-Hellman for session key generation, and AES\index{Advanced Encryption Standard (AES)} for bulk data encryption.

More important than the performance issues with public key cryptography, the security of both RSA and Diffie-Hellman is based on the idea that they are \textbf{\emph{computationally secure}}\index{computational security}.
Anybody listening to the channel is able to record and store the classical messages exchanged.
In principle, an eavesdropper can break the encryption if they have access to a fast enough computer, either now (unlikely) or in the future (harder to guarantee)~\footnote{This is sometimes called ``harvest now, decrypt later''.}.
Therefore, RSA and Diffie-Hellman are not unconditionally secure~\footnote{Cryptographers are working to replace these mechanisms, in a broad push called \emph{post-quantum cryptography (PQC)}.
As of this writing, the first major phase of this process is nearing completion.}.
A crucial point is that quantum computers can in principle break some computationally secure protocols, notably RSA and Diffie-Hellman, with relative ease~\footnote{The details of this possibility are a very long discussion, but what you read in the popular press often over-simplifies this issue.}.
So, how can we actually establish a secure connection between Alice and Bob?
% An alternative is to use some generator, some hypothetical device, that can generate a secret key, then that key is shared with Alice and Bob in some secure fashion. Once Alice and Bob are sharing some correlated secret key that only they know they can use it to encrypt their messages. For example, Bob encrypts a message, then sends it to Alice, who uses her knowledge of the secret key to decrypt it and read the message.

The bulk encryption mechanism can be AES, introduced in the last section, but the details are beyond the scope of this book.
Alternatively, we can encrypt one bit of message using one bit of the key. 
One way to do this is by using an exclusive-OR operation (XOR).
Its truth table is shown in Tab.~\ref{tab:xor_truth_table}.
\begin{table}[t]
    \setcellgapes{5pt}
    \renewcommand\theadfont{}
    \makegapedcells
    \centering
    \begin{tabular}{ccc}
        \hline
        \textbf{Input bit $a$} & \textbf{Input bit $b$} & \textbf{Output bit $c$} \\
        \hline
        0 & 0 & 0 \\
        0 & 1 & 1 \\
        1 & 0 & 1 \\
        1 & 1 & 0 \\
        \hline
    \end{tabular}
    \caption[XOR operation.]{Truth table for the XOR operation.}
    \label{tab:xor_truth_table}
\end{table}
The output bit $c$ of the XOR operation for two input bits $a$ and $b$ is the following,
\begin{equation}
    c = a \oplus b = \begin{cases}
        0, \quad \text{if } a = b, \\
        1, \quad \text{if } a \neq b.
    \end{cases}
\end{equation}
If $m_i$ is the $i$-th bit of the message, $k_i$ is the $i$-th bit of the key, the $i$-th bit of the ciphertext (encrypted message) is given by $c_i = m_i \oplus k_i$. 
This approach is known as \textbf{\emph{one-time pad}}\index{one-time pad (OTP)}.
This technique cannot be broken, provided that the key was generated in a secure and random fashion and, critically, is used only once.
If Alice has a message of $n$ bits that she would like to send to Bob, she requires a secret key that iss at least $n$ bits long.
Once she uses that key to encrypt her message she cannot use it again. If she has some other thing to say to Bob, they require a completely new and fresh secret key to ensure security.
This makes OTP secure but requires a large number of secret bits.

OTP is actually pretty good in theory, but there is one remaining question if we want to use the one-time pad, and that's how to actually distribute this key.
Perhaps our hypothetical key generator is used only during Alice and Bob's face-to-face meeting.
They could generate enough key bits for a year's worth of communication or more, store them somewhere secure and use when needed.
But, we already know that that is impractical.
Our only alternative is to use the public channels available.
The classical public channel is subject to being recorded, as noted above, but a quantum channel, even if nominally public, offers unique properties that allow us to guarantee that no one is listening in.
We will see how this can be achieved in the next section.




%%%%%%%%%%%%%%%%%%%%%%%%%
\section{BB84 Protocol}
\label{sec:bb84-protocol}
%%%%%%%%%%%%%%%%%%%%%%%%%

BB84 is a quantum protocol for generating a string of shared and secret classical bits between two parties.
Alice and Bob can utilize a public quantum channel, as well as their public classical channel.
The key is established through appropriately initialized qubits which are communicated by Alice over the quantum channel, and measured by Bob.
Classical information is exchanged between Alice and Bob over the classical channel.
The protocol has the following four stages:
\begin{itemize}
    \item Qubit preparation,
    \item Quantum communication,
    \item Classical communication,
    \item Classical post-processing.
\end{itemize}
Let's discuss these stages in more depth.

\emph{Qubit preparation.}
Alice begins the protocol by generating two $n$-bit random strings, denoted by $a$ and $b$,
\begin{align}
    a & = a_1 a_2 \ldots a_n, \\
    b & = b_1 b_2 \ldots b_n,
\end{align}
where $a_i$ and $b_i$ are the $i$-th bits of bit strings $a$ and $b$, respectively.
Alice uses the values of individual bits from $a$ and $b$ to prepare her qubits in a very particular way.
The basis for the encoding is determined by the bit string $b$, while a particular state of the qubit is chosen according to the bit string $a$.
Qubit $i$ is encoded in the Pauli $Z$ basis if $b_i=0$, and in the Pauli $X$ basis if $b_i=1$.
If bit $a_i=0$ then the qubit is prepared in the +1 eigenstate of the chosen basis.
If $a_i=1$ then the qubit is prepared in the -1 eigenstate of the chosen basis.
I short,
\begin{equation}
    a_i = \begin{cases}
        0 \rightarrow +1\text{ eigenstate}, \\
        1 \rightarrow -1\text{ eigenstate},
    \end{cases}
    \quad
    b_i = \begin{cases}
        0 \rightarrow Z\text{ basis}, \\
        1 \rightarrow X\text{ basis}.
    \end{cases}
\end{equation}
Writing the state of qubit $i$ as \ket{\psi_{a_ib_i}}, we have the following four possible states that Alice will prepare,
\begin{equation}
    \ket{\psi_{00}} = \ket{0}, \quad \ket{\psi_{10}} = \ket{1}, \quad \ket{\psi_{01}} = \ket{+}, \quad \ket{\psi_{11}} = \ket{-}.
    \label{eq:BB84-four-states}
\end{equation}
The full state of all $n$ qubits that Alice prepares is given by the tensor product of the states of individual qubits,
\begin{equation}
    |\psi\rangle=\bigotimes_{k=1}^n\left|\psi_{a_k b_k}\right\rangle.
\end{equation}

Notice that the four states in Eq.~(\ref{eq:BB84-four-states}) that Alice prepares are not all orthogonal.
For example, if we take the inner product between \ket{\psi_{00}} and \ket{\psi_{01}}, we get,
\begin{equation}
    \braket{\psi_{00}}{\psi_{01}} =\frac{1}{\sqrt{2}} \neq 0.
\end{equation}
In this particular case, the inner product is $1/\sqrt{2}$. It will be the same if we take, for example, 
$\braket{\psi_{10}}{\psi_{11}} = 1/\sqrt{2} \ne 0$.
When the inner product is non-zero, it means that the two states are not perfectly distinguishable.
This observation is a crucial ingredient in the BB84 protocol. 

Why is this non-distinguishability important?
It is not used directly in the generation of the key but it is necessary if Alice and Bob have a suspicion that a third malicious party is trying to eavesdrop on their conversation.

Let's look at an example of the encoding, shown in Tab.~\ref{tab:bb84-example}.
Let's say that Alice generates the two random strings $a = 01101$ and $b=11001$.
She starts encoding.
First, she looks at the first bit in her string $b$, which is $1$, so she knows, ``Now I have to encode in the $X$ basis'', and the state that she prepares is a \ket{+} state because her first bit in the $a$ string is a $0$.
To prepare the second qubit, she looks at the second bit in her string $b$, which is again $1$, so again she knows she has to prepare a state from the $X$ basis, and the state is given by the second bit in string $a$, which is $1$, therefore she prepares the state \ket{-}.
She goes on until she prepares all five qubits.
\begin{table}
    \setcellgapes{3pt}
    \renewcommand\theadfont{}
    \makegapedcells
    \centering
    \begin{tabular}{cccccc}
        \hline
        & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} \\
        \hline
        \boldmath$a_i$ & 0 & 1 & 1 & 0 & 1 \\
        \boldmath$b_i$ & 1 & 1 & 0 & 0 & 1 \\
        \textbf{Encoding basis} & $X$ & $X$ & $Z$ & $Z$ & $X$ \\
        \textbf{Encoded qubit} & \ket{+} & \ket{-} & \ket{1} & \ket{0} & \ket{-} \\
        \hline
    \end{tabular}
    \caption[BB84 encoding example.]{Alice encodes the qubits she wishes to communicate, choosing a basis using a bit from $b$ and an eigenstate based on the corresponding bit from $a$.}
    \label{tab:bb84-example}
\end{table}

\emph{Quantum communication.}
Alice sends the prepared qubits to Bob over the public quantum channel. Let's consider what Bob knows at this time.
Alice has not shared the secret string $b$ containing information about the preparation basis with him.
All Bob knows is that he is receiving qubits that could be any of the four possible states \ket{0}, \ket{1}, \ket{+} or \ket{-}.
He creates his own random bit string $b'$.
Because he's expecting $n$ qubits, he generates $n$ bits: $\{b'_1, b'_2, \ldots b'_n\}$.
He uses this bit string to pick the basis for measuring each of the qubits he receives.
If $b'_i=0$, he measures qubit $i$ in the Pauli $Z$ basis.
If $b'_i=1$, he measures qubit $i$ in the Pauli $X$ basis.
If the outcome of the $i$-th measurement is $+1$, he assigns $0$ to bit $a'_i$.
If the outcome is $-1$, he assigns $1$ to bit $a'_i$.
This way Bob generates a new random string of bits $a'$.

% Let's consider the case where we are measuring in the $Z$ basis, and we are given two states. Assume one state is \ket{0}, and the other state is \ket{1}. If this happens, we see that they are orthogonal, and we can perfectly distinguish them. So if we just keep measuring the incoming qubits, if the qubit is in \ket{0}, we will always get a $+1$ outcome. On the other hand, if the qubit is in \ket{1}, we will always get a $-1$ outcome. With certainty, we can distinguish whether the incoming qubit is a \ket{0} or a \ket{1}.

% The same thing applies if we are measuring in the $X$ basis, and we are given only \ket{+} or \ket{-}. If we keep measuring in $X$ and we are given the \ket{+} state, then the outcome will be always $+1$ with hundred percent probability. If, on the other hand we are given the \ket{-} state, and we measured in the $X$ basis, we will get outcome $-1$ all the time. In this sense, we can distinguish plus and minus if we're measuring in the $X$ basis.

% To see the problem, let's say that we are given the state \ket{0} or \ket{+}, and we measure in the $Z$ basis. So if we measure the \ket{0} state, as above we always get the $+1$ outcome. If we measure the second state, the \ket{+} state, there's a fifty percent probability that we get the outcome $+1$ and fifty percent probability that we get the outcome $-1$.

% So, if we are given a state \ket{0}, all is good, but if we are given the state \ket{+}, sometimes we will get a $+1$ and sometimes we will get a $-1$. If our measurement result is $-1$, fine, we can say we know that this state is \ket{+}, but if we get the $+1$ outcome, we are unsure whether the state we were given was a \ket{+} or whether it was a \ket{0}. In this sense, the states are non-distinguishable. We can do the same thing in the $X$ basis. With certainty, we can say that we get a $+1$ outcome if we were given a \ket{+}, but if we were given a \ket{0}, sometimes it will be a $+1$ and sometimes a $-1$.

\emph{Classical communication.}
Next, Alice and Bob share classical information with each other over the public classical channel.
Alice shares her randomly generated bit string $b$, and Bob shares his randomly generated bit string $b'$.
This exchange shares information about the basis in which the qubits were prepared and in which they were measured.

Does this classical communication compromise the security of the protocol?
After all, the strings $b$ and $b'$ are used in generating the secret key.
Sharing of these two random bit strings does not make the protocol insecure, provided the communication occurs \textbf{\emph{after}} the qubits are measured by Bob.

\emph{Classical post-processing.}
If Bob measured in the same basis that Alice used during the preparation of the qubit, they will keep the corresponding bits from $a$ and $a'$.
If they measured in different bases, then they just discard the bits $a_i$ and $a'_i$.
If Alice prepares a qubit in a certain basis and Bob measures it in the same basis, the two possible states are orthogonal, meaning they are perfectly distinguishable by the measurement in that basis.
We denote the bits that they keep as $\bar{a}$ and $\bar{a}'$.
These bits are perfectly correlated, meaning that these two shorter bit strings that they generated are equal.
Finally, Alice and Bob share a secret key that they can use to encrypt their message.

Let's look at an example, again considering a case where $n=5$, as shown in Tab.~\ref{tab:complete-bb84}.
Alice has randomly generated two five-bit strings, $a$ and $b$.
Bob generates his own random $b'$ string.
This bit string is different from Alice's $b$ because he does not know Alice's $b$ at this time.
He measures in the basis given by $b'$.
You can see that in the first position Alice's preparation basis and Bob's measurement basis agree, so their classical bits of the secret key $\bar{a}_1$ and $\bar{a}'_1$ are the same.

On the other hand, Alice prepared the second qubit in the $Z$ basis.
Bob's random bit $b'_2 = 1$, meaning that he measured it in the $X$ basis.
With fifty percent probability he will obtain $+1$, with fifty percent probability he will obtain $-1$.
Therefore Alice and Bob cannot be sure that they are really sharing a correlated bit, therefore they discard it.
For the third qubit, $b_3 = b'_3$ and again Alice prepared in the same basis as Bob measured.
Alice and Bob know with certainty their classical bits are correlated Therefore they keep them as part of the secret key..
In this way, they are keeping a random subset of the bits, leaving a shorter string of key bits, all of which are one hundred percent correlated.
The shared key that they have is given by $\bar{a} = \bar{a'} = \{1, 0, 1\}$, as marked with the check marks in the table.


\begin{table}
\setcellgapes{3pt}
    \renewcommand\theadfont{}
    \makegapedcells
    \centering
    \begin{tabular}{cccccc}
        \hline
        & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} \\
        \hline
        \boldmath$a_i$ & 0 & 1 & 1 & 0 & 1 \\
        \boldmath$b_i$ & 1 & 1 & 0 & 0 & 1 \\
        \textbf{Alice's basis} & $X$ & $X$ & $Z$ & $Z$ & $X$ \\
        \textbf{Encoded qubit} & \ket{+} & \ket{-} & \ket{1} & \ket{0} & \ket{-} \\
        \boldmath$b'_i$ & 1 & 1 & 1 & 0 & 0 \\
        \textbf{Bob's basis} & $X$ & $X$ & $X$ & $Z$ & $Z$ \\
        \boldmath$a'_i$ & 1 & 0 or 1 & 0 & 0 or 1 & 1 \\
        \textbf{keep or discard} & \textcolor{mygreen}{\checkmark} & \textcolor{myred}{\xmarksmall} & \textcolor{mygreen}{\checkmark} & \textcolor{myred}{\xmarksmall} & \textcolor{mygreen}{\checkmark} \\
        \boldmath$\bar{a}_i,\bar{a}_i'$ & 1 & - & 0 & - & 1 \\
        \hline
    \end{tabular}
    \caption[A complete BB84 example for five bits.]{A complete BB84 example for five bits.  The check marks indicate bits where the selected preparation and measurement bases agree, giving a bit that can be used in the final agreed-upon key.}
    \label{tab:complete-bb84}
\end{table}

% \rdv{Replace this paragraph with a typeset algorithm (p.31 in slides, without eavesdropper detection; also doesn't have a separate step for exchange of bases)}
% So, here's the summary of the protocol so far: Alice starts by generating two n-bit strings, a and b. "b" is used for basis of the preparation, whereas "a" tells which state of that particular basis Alice should prepare the qubit in. If $b_k$ is equal to zero, then she prepares in the $Z$ basis, if $b_k$ is equal to one, she prepares in the $X$ basis. Then, Alice sends these qubits to Bob over a public quantum channel. Bob measures randomly either in $Z$ or $X$ basis. After the measurements are completed, and only after that, they are allowed to share the information about the preparation basis and the measurement basis, and they keep the bits only where they prepared and measured in the same basis. Again, they do that because they are guaranteed that in this scenario, the results that are generated are hundred percent correlated. And whatever is left of the key, they use as a secret key for encoding and decoding their messages.

So far, we have only considered the ideal scenario where there was no eavesdropper\footnote{In fact, we have not even checked for the presence of an eavesdropper yet.}.
Now let's say that somebody is listening to both the public classical channel and the public quantum channel.
Next, we are going to consider the effect of an eavesdropper, whom we are going to name Eve, and see what effect she has on the protocol and how the protocol can discover the presence of such an eavesdropper.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Eavesdropper detection}
\label{sec:eavesdropper-detection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In the previous section, we saw how the protocol works under idea conditions.
Let's see what happens when we include the effect of an eavesdropper trying to gain access to the secret key that Alice and Bob are generating generate.
This time, we place Eve in between Alice and Bob.
Eve also has access to the public quantum and classical channels that are used to communicate the qubits and to exchange the classical information.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.8\textwidth]{lesson9/eve-copy-and-send.png}
        \caption[Eve's ideal (but impossible) eavesdropping arrangement.]{Eve's ideal eavesdropping arrangement would be to copy the qubits sent by Alice, sending one copy to Bob and keeping the other copy for herself, but the no-cloning theorem makes that impossible.}
    \label{fig:eve-copy-and-send}
\end{figure}

What can Eve do?
Let's imagine that she can intercept the qubits that Alice is sending over the public quantum channel, copy them and then resend them to Bob, as in Fig.~\ref{fig:eve-copy-and-send}.
If she could do that, she could hold her copy of the qubits, wait until Alice and Bob announce the qubit preparation and measurement bases, then measure her copies.
Doing that, she would discover which qubits are used for the generation of the secret key, and she would also know in which basis to measure them in order to generate a key that is perfectly correlated with the one hared between Alice and Bob.
Luckily, it is impossible for Eve to do that due to the no-cloning theorem\index{no-cloning theorem} we saw in the previous Chapter~\ref{sec:8-3_no-cloning}.

If Eve cannot copy the qubits and hold them, then in order to gain any access to the information that Alice is trying to share with Bob, she has to measure the qubits and forward them to Bob.
What can happen in this case?
Remember, the preparation basis stored in the bit string $b$ is still kept secret by Alice.
That basis has not yet been communicated over a public classical channel to Bob.
Without access to this information, Eve has to pick either the $X$ or $Z$ basis at random for her measurement.
Eve therefore runs the risk of disturbing and altering the state of hte qubits that she intercepted from Alice.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.8\textwidth]{lesson9/eve-disturbance.png}
        \caption[Eve's measurements disturb the qubits.]{If Eve tries to measure  the qubits sent by Alice, then send them on to Bob, the disturbance she introduces will be easily detected.}
    \label{fig:eve-disturbance}
\end{figure}

For example, if Alice prepares the qubit in the Pauli $X$ basis, and Eve also measures in the $X$ basis, there is no disturbance to the state of the qubit.
The qubit is still projected onto the same state that it was prepared in, leaving the state of the qubit unchanged.
However, if Alice's preparation basis is the Pauli $Z$ and Eve's measurement basis is the Pauli $X$, things are different.
The qubit originally prepared by Alice was either in \ket{0} or in \ket{1}.
But by measuring in the $X$ basis, Eve is now projecting the qubit onto either the \ket{+} state or the \ket{-} state.
This disturbs the state of the qubit, forcing it into an eigenstate of the wrong basis.
Similarly, where Alice prepares in the $X$ basis and Eve measures in the $Z$ basis, the state will be projected into a different state than the one that was prepared.
This is the main principle Alice and Bob will use to detect the presence of Eve.

Fig.~\ref{fig:eve-disturbance} shows this scenario.
Alice prepares her qubits, then she starts sending them over the public quantum channel.
Eve intercepts and measures them in a randomly chosen basis, and then she passes on these qubits to Bob.
Sometimes, Eve guesses the correct basis, measuring in the preparation basis and leaves the qubits undisturbed.
But sometimes, she chooses the wrong basis for her measurement.
She disturbs some of the qubits, represented by the black qubits in the figure.
This gives Alice and Bob an opportunity to detect that there is an eavesdropper tampering with the qubits.

To detect Eve, Alice and Bob go through with their BB84 protocol.
They compare their preparation and measurement bases, and keep only those bits where they worked in the same basis, making the new, shorter string $\bar{a}$.

Now comes the new part.
Alice and Bob dedicate a portion of the string $\bar{a}$ to detecting the presence of Eve.
First, let's consider one qubit.
Eve has a $50\%$ chance of measuring in the same basis as Alice's preparation basis for the qubit.
Bob also chooses the same basis as Alice with probability $50\%$. Remember, if Alice prepared in one basis and Bob measured in the same basis, they are expecting this classical measurement outcomes to be the same, giving them a perfectly correlated key. But if Eve measured this qubit in the \textbf{\emph{wrong}} basis and disturbed this qubit, she risks being detected.
Of course, if Bob also selected the wrong basis, then Alice and Bob will discard that bit and Eve's disturbance goes undetected -- she got lucky.
But, if Bob picks the right basis when Eve picks the wrong one, then Alice and Bob will assume the bit to be good but there is a chance that the two classical bits will not coincide. If Alice and Bob compare their values for this bit and they don't coincide, then they know that something went wrong and there's an eavesdropper present trying to gain access to their secret key.  

Let's focus on the string $\bar{a}$, which represents the cases where Alice and Bob picked the same basis. 
From $\bar{a}$, Alice and Bob choose (again, it is important that this selection be random) a subset of the measured bits to use to test for the presence of Eve, reserving the rest for the final, secret key.
The chosen classical bits are disclosed by both Alice and Bob, who compare them and look for discrepancies.
Within this set of bits, the potential detection happens when Eve picked the wrong basis, which happens half of the time, at random.
But even in that case, there is a $50\%$ chance that Eve again gets lucky and Bob's subsequent measurement projected the qubit \textbf{\emph{back}} into the original state that Alice prepared.
In that case, when Alice and Bob compare their results, they will find the same values and Eve slips through undetected.
In fact, Alice and Bob only detect Eve with a probability of $1/4$ using a single bit.

The strength of the protocol comes through repetition of this probabilistic test.
Let's say that Alice and Bob choose to use $n$ of the bits for this detection procedure.
Eve has a probability of $3/4$ of passing each individual test, but put them all together and Alice and Bob have an excellent shot at detecting Eve.
For $n$ test bits, the eavesdropper detection probability is
\begin{equation}
P(n)=1-\left(\frac{3}{4}\right)^n.
\end{equation}

In Fig.~\ref{fig:catching-eve}, on the horizontal axis, we plot $n$, the length of the bit string that we have dedicated to detecting the eavesdropper.
On the vertical axis, we have the probability of detection $P(n)$.
When we dedicate only a few bits to detect the eavesdropper, $n$ is very small and the probability that Eve is detected is relatively small.
But very quickly, this probability shoots up to near certainty.
With nearly a 100\% probability, Alice and Bob can detect the presence of an eavesdropper.
Even for $n = 25$, dedicating a mere 25 bits to detecting Eve, the chance is only one in a thousand that Eve will not be detected.
With very high probability, Alice and Bob know that somebody's eavesdropping onto their channel, in which case they say to each other, ``We know that we are not sharing a secure secret key, therefore we choose not to continue with the rest of our communication'', preventing Eve from gaining access to the key bits that Alice and Bob had intended to use to encrypt the sensitive messages they had planned to exchange.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.7\textwidth]{lesson9/9-4_detection.pdf}
        \caption[Probability of detecting the presence of Eve.]{The probability of Alice and Bob detecting the presence of Eve reaches $0.999$ with only $25$ samples.}
    \label{fig:catching-eve}
\end{figure}

From our discussion so far, it would appear that Alice and Bob can distribute a secret key fairly easily using the BB84 protocol.
In particular, any malicious eavesdropper trying to gain information about the secret key seems to be readily discovered using a relatively small number of qubits.
Things are more complicated in real life.
We have discussed the ideal protocol in absence of noise.
Noise can also change the state of the qubits transmitted by Alice.
Qubits affected by noise can flip to their orthogonal state, they can be rotated to a new basis, or more generally, they can become a mixture of pure states.
This means that even in the absence of malicious Eve, there is a substantial probability that some of the qubits reserved for eavesdropper detection will be disturbed and projected onto the wrong state by Bob.
This will lead to Alice and Bob to the erraneous conclusion that someone is trying to eavesdrop on their communication.

In order to avoid this scenario, Alice and Bob must be ready to accept some deviation from the ideal protocol, and make peace with the fact that some level disturbance will be always present.
If the channel is nearly ideal with low levels of noise, the expected amount disturbance is also low.
Noisy channels will result in more disturbance.
The question of what amount of disturbance Alice and Bob are willing to tolerate is crucial.
If they set the acceptable level too high, malicious Eve will have a good chance to go undetected and gain some information about the secret key.
If the acceptable level is set too low, Alice and Bob will have a high chance of unneccessarily rejecting the secret key, leading to a waste of network resources.
Picking the middle ground is a challenging task that goes beyond the scope of this book.

%\rdv{Mention the DOS aspect?}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Existing QKD network testbeds}
\label{sec:existing-qkd-networks}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \rdv{Needs just a little cleanup, and to decide if we are going to try to include figures or not.}

In the previous sections, we saw how Alice and Bob can use quantum mechanics to discover an eavesdropper while generating a secret random key.
The exciting thing about QKD using single photons is that it is not just a theoretical concept that exists only on paper.
It is not even a one-off experimental demonstration under ideal conditions.
QKD networks have been built and tested in the real world.
In this section, we will learn about some of the QKD network testbeds, their capabilities and scale.

The very first network that was built was the DARPA QKD network in 2004.
The network was built in the state of Massachusetts in the USA.
It consisted of ten nodes, and a number of different physical links.
Communication over free space and communication over a fiber were both incorporated, and optical switching allowed different nodes to establish connections.
This setup was unlike any of the previous experimental implementations, where secure quantum communication in the form of a single photon-based QKD was done only on a point-to-point basis over a single link.
This was the first network experiment demonstrating the viability of quantum key distribution in a more realistic setting.
The work was led by Chip Elliott of BBN, and included a version of the IPsec Internet protocol security suite adapted for QKD.
IPsec usually uses the canonical set of RSA or pre-shared secret for authentication, Diffie-Hellman for key establishment, and 3-DES or AES\index{Advanced Encryption Standard (AES)} for bulk data encryption.  In the DARPA QKD network, the Diffie-Hellman process was replaced with keys generated by QKD.

The next experimental testbed, built in Europe around the year 2008, was known as the SECOQC QKD network.
SECOQC stands for ``Secure Communication based on Quantum Cryptography''.
It was launched in Vienna, and it comprised six nodes and eight links. This project developed a layered architecture for the communication services.

Another notable QKD network testbed was built in Tokyo around 2010.
The University of Tokyo Hongo campus and a facility in Otemachi, a place in central Tokyo where many telecommunication providers converge, are separated by only a few kilometers.
The network reached all the way to the National Institute of Information and Communications Technology (NICT) in Kogane, in the western Tokyo suburbs.
The Tokyo QKD network demonstrated for the first time a quantum-secured video conference.
This was another step toward showing that quantum networks are viable in real-world communications.

As of this writing in early 2023, by far the most extensive QKD network in the world is in China.
As of late 2020, the network covered much of the geographic span of China, with 2,000 kilometers of fiber reaching from Shanghai to Beijing and a satellite link that reaches almost to the border with Kazakhstan in Xinjiang.
The eastern fiber network includes 700 individual links, and the network serves 150 users.



\newpage
\begin{exercises}

\exer{
\emph{One-time pad.}
Alice would like to transmit her plaintext message $m$ to Bob, encoding it using the one-time pad with a secret key $k$ that she shares with Bob.
The ciphertext is given by
\begin{equation}
    c = m \oplus k.
\end{equation}
\subexer{
If the plaintext $m$ contains $n$ bits, what is the minimum length of the key?
}
\subexer{
Show that in order to obtain the plaintext $m$, Bob needs to apply the one-time pad to the received ciphertext.
}
\subexer{
Let's say that Alice's plaintext and shared key are
\begin{align}
    m & = 0101010111, \\
    k & = 1010100111,
\end{align}
respectively.
What is the ciphertext?
}
\subexer{
Check that applying the key to the ciphertext decodes the message.
}
}

\exer{
\emph{Two-time pad.}
We mentioned that the one-time pad is secure provided that it is used only once.
Let's consider the scenario where Alice communicates two messages $m_1$ and $m_2$, but she is careless and uses the same key $k$ to encode them before transmission.
Since the same key is used twice, it is called two-time pad.
\subexer{
Write down the two ciphertexts corresponding to Alice's messages. 
}
\subexer{
Eve intercepts both transmissions.
What information about Alice's messages $m_1$ and $m_2$ can she obtain and how? 
}
}

\exer{
\emph{Indistinguishability of quantum states.}
In Sec.~\ref{sec:bb84-protocol}, we asserted that \ket{0} and \ket{+} are not orthogonal, and made statements about measurement probabilities without working through the mathematics.
\subexer{
Prove that the states are not orthogonal.
}
\subexer{
Find the probability of the $\pm 1$ outcomes when measuring both of those states in the $Z$ basis, using calculations similar to those in Sec.~\ref{sec:measurement}.
}
\subexer{
Find the probability of the $\pm 1$ outcomes when measuring both of those states in the $X$ basis, using calculations similar to those in Sec.~\ref{sec:measurement}.
}
}

\exer{
\emph{Biased random number generator.}
Consider the scenario where Eve secretly tampers with Alice's random number generator and changes its output to be biased,
\begin{equation}
    P(0) = \frac{1}{4}, \quad\text{and } \quad P(1) = \frac{3}{4}.
\end{equation}
This random number generator is used by Alice to generate both of her random bit strings $a$ and $b$, as well as Eve's choice of measurement basis.
Bob's random number generator is not compromised.
\subexer{
What are Alice's probabilities of preparing each of the basic encoding state,
\begin{equation}
    P(\ket{0}), \quad P(\ket{1}), \quad P(\ket{+}), \quad P(\ket{-})?
\end{equation}
}
\subexer{
What is the probability that Eve disturbs the intercepted state by measuring it in the wrong basis?
}
\subexer{
What is the probability that Bob projects a disturbed state onto the wrong state?
}
\subexer{
What is the probability that Alice and Bob detect Eve in a single round?
How does this chance compare to the case of ideal random number generator?
}
}



\end{exercises}