Browse the glossary using this index

Special | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | ALL
Picture of Yee Wei Law

BB84: Overview

by Yee Wei Law - Thursday, 26 October 2023, 2:27 PM
 

Quantum key distribution (QKD) is a method for generating and distributing symmetric cryptographic keys with information-theoretic security based on quantum information theory [ETS18].

A QKD protocol establishes a secret key between two parties β€” let us call them πŸ‘© Alice and πŸ§” Bob as per tradition β€” connected by 1️⃣ an insecure quantum channel and 2️⃣ an authenticated classical channel [Gra21, Sec. 3.1].

  • The established key can be however long as required so that it can serve as the key in a one-time pad.
  • β€œAuthenticated” does not imply β€œconfidential” and does not necessarily require the use of cryptography. Alice and Bob can physically meet and verify each other’s identity.
  • In practice, the authenticated classical channel can be established using 1️⃣ a pre-shared symmetric key, or 2️⃣ public-key cryptography [PAB+20, Sec. F].

A QKD protocol typically proceeds in two phases [Wol21, Ch. 4]:

  1. the quantum transmission phase, in which πŸ‘© Alice and πŸ§” Bob send and/or measure quantum states;
  2. the classical post-processing phase, where the bitstrings generated in the previous phase are converted into a pair of secret keys.

The security of QKD hinges on the principles of quantum mechanics, rather than the hardness of any computational problem, and hence does not get threatened by advances in computing technologies.

  • During the quantum transmission phase, any adversary β€” let us call it 😈 Eve as per tradition β€” eavesdropping on the quantum channel inherently disturbs the channel and interrupts the key establishment process.
  • Eve cannot make a copy of any transmitted state (that contributes to the key to be established) thanks to the no-cloning theorem.
Theorem 1: No-cloning theorem [WZ82]

It is not possible to perfectly clone an unknown quantum state.

The earliest QKD protocol is due to Bennett and Brassad [BB84] and is called BB84, named after the authors and the year it was proposed.

QKD leverages physical mechanisms, so unavoidably we need to discuss the physical mechanisms that underlie/enable BB84, which are based primarily on the polarisation of photons [Wol21, Sec. 1.3.1].

Polarisation

The polarisation of photons specifies the geometrical orientation of the oscillation of its electromagnetic field.

  • Polarisation is linear if the field only oscillates in one direction.
  • Polarisation is circular if the field rotates in a plane as the wave propagates.

We only consider linear polarisation here. For linear polarisation, we distinguish between two bases:

  • rectilinear basis, which includes horizontal and vertical orientations; and
  • diagonal basis, which is essentially the rectilinear basis rotated by ; as shown in Fig. 1.
Fig. 1: Polarisation bases and filters [Wol21, Fig. 1.4].

Consider the effect of polarisation filters depicted in Fig. 1:

  • When a ↕ vertically polarised photon passes through a rectilinear polarisation filter, it is deflected to the right (➑).
  • When a ↔ horizontally polarised photon passes through a rectilinear polarisation filter, it is deflected to the left (β¬…).
  • When a diagonally polarised photon passes through a rectilinear polarisation filter, it is equally likely to be deflected to the left and right.

Thus, measuring a diagonally polarised photon in the rectilinear basis, and similarly measuring a vertically/horizontally polarised photon in the diagonal basis, give a random result.

  • We call the rectilinear and diagonal bases mutually conjugate (see Definition 1).

    Definition 1: Conjugate bases

    Two bases are mutually conjugate [BB84; FGG+97] or unbiased [Wol21, p. 9] if each vector of one basis has equal-length projections onto all vectors of the other basis.

  • The Heisenberg uncertainty principle ensures that when making two sequential measurements using conjugate bases, the system is disturbed in such a way that the uncertainty of the measurement outcome is maximised [Woj22, p. 42].

With knowledge of polarisation in mind, let us now discuss the quantum transmission phase of BB84, which involves encoding of classical bits into quantum states, communication over a quantum channel, and decoding of quantum states into classical bits.

Quantum transmission phase

This phase of the protocol involving πŸ‘© Alice and πŸ§” Bob goes like this [Wol21, Sec. 1.3.2]:

  1. πŸ‘© Alice chooses a string of random classical bits: .
  2. πŸ‘© Alice chooses a random sequence of rectilinear (Z) bases and diagonal (X) bases; these are called the canonical bases [Dua14, p. 295].
  3. πŸ‘© Alice encodes her bitstring into a collection of photons with basis-dependent polarisation.

    In the rectilinear basis, 0 and 1 are encoded as β†’ and ↑ respectively.

    In the diagonal basis, 0 and 1 are encoded as β†— and β†– respectively.

  4. When πŸ§” Bob receives the photons, he randomly (and independently of Alice) decides for each photon whether to measure/decode it in the rectilinear or diagonal basis to retrieve the classical bit.
  5. At the end of this quantum transmission phase, πŸ‘© Alice and πŸ§” Bob each holds a classical bit string, denoted for Alice and for Bob. and form the raw key pair.

An illustration of the process above can be found Fig. 1.

Fig. 1: In steps 1-3, πŸ‘© Alice and πŸ§” Bob engage in the quantum transmission phase, while 😈 Eve eavesdrops on the transmission and attempts to recover the raw key bits. ⚠ The mapping of 0 and 1 in the diagonal basis illustrated here is different from that in the earlier discussion, which follows the original paper [BB84]. In steps 4-5, πŸ‘© Alice and πŸ§” Bob engage in the sifting step, discussed in the next section. Diagram from [LCPP22, Fig. 2a].

Since the polarisation state of each photon is a discrete variable, BB84 is an example of a discrete-variable quantum key distribution (DV-QKD) scheme.

BB84 is also an example of a prepare-and-measure protocol, because of the preparation action of πŸ‘© Alice and the measurement action of πŸ§” Bob.

Classical post-processing phase

This phase of the protocol involves πŸ‘© Alice and πŸ§” Bob exchanging a sequence of classical information in the classical channel to transform their raw key pair into a shared secret key [Wol21, Sec. 1.3.3]:

  1. This is the sifting step (steps 4-5 in Fig. 1):
    • πŸ§” Bob publicly announces the bases he has chosen to measure the photons Alice has sent.
    • πŸ‘© Alice compares Bob’s bases to the ones she used and confirms which bases Bob has chosen correctly.
    • πŸ‘© Alice and πŸ§” Bob discard all the bits for which the encoding and measurement bases are not the same.
  2. This is the parameter estimation step:
    • πŸ‘© Alice and πŸ§” Bob want to compute an estimate of the quantum bit error rate (QBER) in the quantum channel, i.e., the fraction of bits where and differ in the Z and X bases [Gra21, p. 38].
    • For this, πŸ§” Bob reveals a random subset of his key bits.
    • In case of no eavesdropping, these bits should be the same as Alice’s bits and πŸ‘© she confirms them.
    • If the QBER is too high, πŸ‘© Alice and πŸ§” Bob suspect eavesdropping and abort the protocol.
    • The bits that have been revealed during this step are discarded as their information is now public to eavesdroppers.
  3. Computation of the final key if the error rate is not too high:
    • πŸ‘© Alice and πŸ§” Bob perform steps, which were later additions to the original BB84 [BBR88], to correct errors in their keys and increase the secrecy of their key.
    • The first step is error correction (also called information reconciliation), where they erase all errors in their bit strings. After this step, they hold identical strings.

      Direct vs reverse reconciliation [GG02; Djo19, p. 7; PAB+20, Sec. B]

      β–Ά Direct reconciliation: πŸ‘© Alice sends correction information and πŸ§” Bob corrects his key elements to have the same values as Alice’s.

      • For example, πŸ‘© Alice performs low-density parity check (LDPC) encoding and sends the parity bits to πŸ§” Bob, who in turn performs LDPC decoding.
      • Error correction fails when quantum channel loss exceeds 50%.

      β—€ Reverse reconciliation: πŸ§” Bob sends correction information and πŸ‘© Alice corrects her key elements to have the same values as Bob’s.

      • For example, πŸ§” Bob performs LDPC encoding and sends the parity bits to πŸ‘© Alice, who in turn performs LDPC decoding.
      • Preferred option to direct reconciliation.
      • Provides a usable key when the mutual information of Alice () and Bob () exceeds the mutual information of Bob and Eve (), i.e., ; the difference between these two terms gives the asymptotic secret key rate.
    • The second step is privacy amplification, which is a procedure that minimises Eve’s knowledge of the key.

Table 1 shows an example of an exchange between πŸ‘© Alice and πŸ§” Bob in the absence of eavesdropping.

Table 1: An example of an exchange between πŸ‘© Alice and πŸ§” Bob in BB84 in the absence of eavesdropping [Wol21, Table 1.2].

For discussion of physical realisations of BB84, follow this knowledge base entry.

Performance and security evaluation

In terms of performance, a basic figure of merit of every QKD protocol is the secret key rate, i.e. the fraction of secure key bits produced per protocol round.

For security, follow this overview of QKD security.

References

[BB84] C. H. Bennett and G. Brassard, Quantum cryptography: Public key distribution and coin tossing, in Proceedings of the International Conference on Computers, Systems & Signal Processing, December 1984, pp. 175–179. Available at https://arxiv.org/abs/2003.06557.
[BBR88] C. H. Bennett, G. Brassard, and J.-M. Robert, Privacy amplification by public discussion, SIAM Journal on Computing 17 no. 2 (1988), 210–229. Available at https://www.proquest.com/docview/919828123.
[Djo19] I. B. Djordjevic, Physical-Layer Security and Quantum Key Distribution, Springer Cham, 2019. https://doi.org/10.1007/978-3-030-27565-5.
[Dua14] F. Duarte, Quantum Optics for Engineers, CRC Press, 2014. https://doi.org/10.1201/b16055.
[ETS18] ETSI, Quantum Key Distribution (QKD); Vocabulary, Group Report ETSI GR QKD 007 v1.1.1, December 2018. Available at https://www.etsi.org/deliver/etsi_gr/QKD/001_099/007/01.01.01_60/gr_qkd007v010101p.pdf.
[FGG+97] C. A. Fuchs, N. Gisin, R. B. Griffiths, C.-S. Niu, and A. Peres, Optimal eavesdropping in quantum cryptography. i. information bound and optimal strategy, Phys. Rev. A 56 no. 2 (1997), 1163–1172. https://doi.org/10.1103/PhysRevA.56.1163.
[Gra21] F. Grasselli, Quantum Cryptography: From Key Distribution to Conference Key Agreement, Quantum Science and Technology, Springer Cham, 2021. https://doi.org/10.1007/978-3-030-64360-7.
[GG02] F. Grosshans and P. Grangier, Reverse reconciliation protocols for quantum cryptography with continuous variables, arXiv preprint quant-ph/0204127, 2002. https://doi.org/10.48550/arXiv.quant-ph/0204127.
[LCPP22] C.-Y. Lu, Y. Cao, C.-Z. Peng, and J.-W. Pan, Micius quantum experiments in space, Rev. Mod. Phys. 94 no. 3 (2022), 035001. https://doi.org/10.1103/RevModPhys.94.035001.
[PAB+20] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. Shamsul Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden, Advances in quantum cryptography, Advances in Optics and Photonics 12 no. 4 (2020), 1012–1236. https://doi.org/10.1364/AOP.361502.
[Woj22] F. Wojcieszyn, Introduction to Quantum Computing with Q# and QDK, Quantum Science and Technology, Springer Cham, 2022. https://doi.org/10.1007/978-3-030-99379-5.
[Wol21] R. Wolf, Quantum Key Distribution: An Introduction with Exercises, Springer, Cham, 2021. https://doi.org/10.1007/978-3-030-73991-1.
[WZ82] W. K. Wootters and W. H. Zurek, A single quantum cannot be cloned, Nature 299 no. 5886 (1982), 802–803. https://doi.org/10.1038/299802a0.
Tags: