BB84

The OG quantum cryptographic protocol

Code : Cirq

BB84 is a quantum key distribution (QKD) protocol developed by Charles Bennett and Gilles Brassard in 1984.

BB84 relies on two pillars of quantum physics

- the no-cloning theorem - it is impossible to copy an arbitrary quantum state without knowing what it is, and

- the wavefunction collapse - measuring a quantum state in a superposition irreversibly collapses it into 1 of the possible eigenstates.

Objective

Alice and Bob are physically separate and want to exchange messages securely. One way is to generate a secret key that only Alice and Bob know and use that to encrypt messages. Keys that are reused can be guessed by eavesdroppers so key distribution protocols are used to securely generate and distribute new secret keys.

Prerequisites

• Alice and Bob can communicate via a classical channel.

• Alice can also prepare qubits in any state and send them to Bob using a unidirectional quantum channel.

Running the protocol

1. Alice generates two random binary strings a and b of length n. String a encodes the state String b encodes the basis

2. She then prepares n qubits according to the following prescription: $|q\rangle_i = \begin{cases} |0\rangle, & \text{if } & a[i] == 0 & \text{and } & b[i] == 0 \\ |1\rangle, & \text{if } & a[i] == 1 & \text{and } & b[i] == 0 \\ |+\rangle, & \text{if } & a[i] == 0 & \text{and } & b[i] == 1 \\ |-\rangle, & \text{if } & a[i] == 1 & \text{and } & b[i] == 1 \end{cases}$

3. Alice sends her qubits to Bob.

4. Bob then generates a random binary string c of length n which encodes the measurement basis..

5. Bob measures the qubit $|q\rangle_i$ in the $\{|0⟩, |1⟩\}$ basis if $c[i] == 0$ and in the$\{|+⟩,|-⟩\}$ basis if $c[i]==1$ and stores the result in a string m.

6. Alice and Bob then announce the strings b and c.

7. The bits of m where b and c match are now known to both Alice and Bob.

Example

Alice's message a : 10111100 # randomly generated Alice's basis b : 01000101 # randomly generated Bob's basis c : 01111111 # randomly generated

Alice sends Bob the qubits.

Bob's measurement result m : 10XXX1X0, where X is indicates the the bit could be either 1 or 0.

When b and c are revealed, both Bob and Alice can deduce that the matching bits form the secret key : 1010.

Best case

BB84 is secure against intercept-and-resend attacks.

Suppose an eavesdropper Eve intercepts all of Alice's qubits and measures them in a randomly guessed basis. Then Eve prepares set of qubits and sends it to Bob. Eve cannot clone the exact state Alice prepared (no-cloning theorem) nor leave it unchanged after measurement (wavefunction collapse). So if Eve takes any action, Alice and Bob will not measure the same key k. So the first message Alice sends is encrypted with k, Bob will not be able to decrypt the message, thus detecting Eve's presence.

Worst case

The worst case is when Eve correctly guesses the basis of the bits where Alice and Bob's bases match. The probability of that happening scales as $2^{-n}$ where n is the number of qubits. Therefore the more qubits, the lower the chance of Eve eavesdropping and getting away with it.

Real case

In the real world, loss and noise complicates the protocol since It becomes harder to tell if a mismatch is due to Eve or random noise.