Implementation of the BB84 QKD protocol

The BB84 protocol for quantum key distribution is implemented in QuCrypt similarly to the way it was described in "Experimental Quantum Cryptography" [Journal of Cryptology, vol. 5, no. 1, 1992]. In the following we list all important steps and give some details of implementation.  We also show how Alice (the initiator) can configure the protocol settings before the execution. An example of the output produced by the execution of the BB84 protocol can be found here. A security analysis of our implementation according to our experimental setting can be found here.
 

The BB84 QKD protocol:

  1. (quantum transmission) The BB84 quantum transmission is executed.
  2. (bases announcement) Alice announces the bases to Bob and Bob announces the positions he measures in the right bases. Let N be the number of remaining bits. The key shared at this point is called the raw key (note that it is not really shared since Alice's and Bob's version are different).
  3. (error estimation) Alice announces a subset of positions of size K and the bit values for those positions in the raw key. Bob also returns the bits he received in those positions. Both players compute the observed error-rate e and accept the quantum transmission if  e <= emax as set initially by Alice. They finally remove the K bits announced from the raw key .  If e >emax then Alice and Bob abort.
  4. (reconciliation) Alice and Bob perform an interactive reconciliation protocol releasing an extra R parity bits about the reconciled key which is the corrected version of the raw key (see below). If the resulting error-rate ereal > emax then Alice and Bob abort.
  5. (confirmation) Alice selects L random subsets X1,...,XL of positions and announces Xi together with the parity of all bits in Xi for 1<= i <= L. Bob compares the parity bits announced  by Alice to the one he gets with his bits and tells Alice whether they are all the same. If some parity bits do not match then Alice and Bob abort.
  6. (privacy amplification) Alice announces to Bob the description of a randomly selected hashing function f from N-K bits to N-K-L-R-S secret bits (see below). They each applies f on the reconciled key in order to get the final secret-key Xf in {0,1}N-K-L-R-S.

Initial Configuration

Alice is responsible to setup the configuration for the protocol execution. This can be done by settings the values in the configuration panel. The panel looks as follow:

The length of the raw key here is different than the value of N defined above.  It is length of the quantum transmission before the bases are announced. This is the number of pulses received by Bob and measured in whatever basis.  If M is the value selected (here in the example we have M=500), then the  value of N is approximatively M/2.

The porportion for sample is the number of random positions among N that have been received by Bob and measured in the right bases that are going to be sampled for error-rate estimation. In the example above, 0.1N positions will be used in order to compute the observed error-rate e.

The size of confirmation sample is the value for L as defined in the protocol description . In the example above, 10 random subsets will be picked and their parity exchanged.  The reconciled key will be identical except with probability at most 2L whenever the confirmation phase succeeds.

The proportion for PA allows to set the value of S as described in the protocol description.  In the example above, we the  S=0.05(N-K) will be selected.   This is the value for the extra-shrinking parameter in privacy amplification. See the security analysis for more information about this.

The last option allows for the transmission of an encrypted short message after QKD has been executed with success. This is mainly for demonstration purposes.

Bases Announcement and Error Estimation

The bases announcement and the error estimation are both performed in the  PlainBB84 class .  The result of this phase is the raw key.

Reconciliation and Confirmation

Reconciliation has been implemented using protocol CASCADE (see proceedings of Eurocrypt'93,p.410). It is a parity-based and interactive error-correction algorithm. Although CASCADE requires a lot of interaction thus slowing down the rate at which secret-key generation can be achieved, it allows to save more bits of key after privacy amplification. If the quantum channel is an expensive ressource then it is probably better to spend more time during reconciliation in order to save more final bits. Moreover, the saving of more bits also means that  for a fixed error-rate, secure key distribution can be achieved over  longer distances. On the other hand, if for some settings the rate at which the secret-key is generated is the main concern, using  a less interactive version of CASCADE might be preferable (especially when the classical channel is slow like the internet). We use the fully interactive version of CASCADE in order to get R as close to Shannon's lower bound (N-K)h(e) as possible.   Reconciliation is the most time consuming operation in the classical phase. Under our experimental conditions, it requires a time comparable to what is needed for raw key generation. Interaction is very expensive on the internet.  CASCADE is implemented in the Cascade class.

Confirmation is implemented the obvious way and allows to make sure that Alice and Bob are sharing identical  keys (which is not completely secret). In particular and for a given L, the probability that Alice and Bob think they share identical keys while in fact they don't is no more than 2-L.

Reconciliation and confirmation for the BB84 scheme are implemented in the RecBB84 class .

Privacy Amplification

Privacy amplification consists for Alice in choosing randomly  a hashing function  f:{0,1}N-K -> {0,1}N-K-L-R-S from some class F. She then announces the description of f over the public channel allowing Alice and Bob to compute the final key Xf=f(XA)=f(XB) where XA and XBare the partially secret strings in {0,1}N-K obtained after confirmation. In order for privacy amplification to produce a statiscally secret Xf, the class F must be  universal2 (see BBR). Moreover, in order for privacy amplification to be efficient, the description of f  in F should be short. We've  implemented privacy amplification using an universal2 class of  hashing functions F introduced by Krawczyk. Any function f in F  is described by a Toeplitz matrix Ts where s in {0,1}2N-2K-L-R-S is randomly selected and sufficient for describing  f.  As a result, the description of  f requires the transmission of only O(N) bits (one-way communication) and time in O(N2) for evaluating it. This makes the contribution of privacy amplification to the secret-key generation rate almost negligeable.

Privacy amplification for the BB84 scheme is implemented in the BB84 class.