Reconciliation is the technique needed to ensure that Claude's and Dominique's key elements are equal. Starting from outcomes of the random variables X and Y , they wish to agree on an equal string Ψ. In this chapter, I will first give some general properties and then overview and introduce several classes of reconciliation techniques. Problem description The goal of the legitimate parties is to distill a secret key, i.e., to end up with a shared binary string that is unknown to Eve. We assume as a convention that Claude's outcomes of X will determine the shared key K . The common string Ψ before privacy amplification can thus be expressed as a function Ψ( X ). Reconciliation consists in exchanging messages over the public classical authenticated channel, collectively denoted M , so that Dominique can recover Ψ from M and the outcomes of Y . If we denote as x 1… l a vector of l independent outcomes of X , the string can be compressed to obtain about lH (Ψ( X )) common uniform bits. As explained in Chapter 6, the impact of reconciliation on privacy amplification is a decrease of | M | bits in the key length, where | M | is the number of bits exchanged during reconciliation. Our goal is thus to maximize lH (Ψ( X ))-| M |, or if Ψ is given, to minimize the number | M | of disclosed bits. Characteristics of reconciliation protocols Before dealing with the details of reconciliation, let us here review some of its characteristics. First, reconciliation can be either one-way or interactive . The first case is obviously only possible with one-way secret-key distillation, as information is sent only from Claude to Dominique.
Reconciliation is the technique needed to ensure that Claude's and Dominique's key elements are equal. Starting from outcomes of the random variables X and Y , they wish to agree on an equal string Ψ. In this chapter, I will first give some general properties and then overview and introduce several classes of reconciliation techniques. Problem description The goal of the legitimate parties is to distill a secret key, i.e., to end up with a shared binary string that is unknown to Eve. We assume as a convention that Claude's outcomes of X will determine the shared key K . The common string Ψ before privacy amplification can thus be expressed as a function Ψ( X ). Reconciliation consists in exchanging messages over the public classical authenticated channel, collectively denoted M , so that Dominique can recover Ψ from M and the outcomes of Y . If we denote as x 1… l a vector of l independent outcomes of X , the string can be compressed to obtain about lH (Ψ( X )) common uniform bits. As explained in Chapter 6, the impact of reconciliation on privacy amplification is a decrease of | M | bits in the key length, where | M | is the number of bits exchanged during reconciliation. Our goal is thus to maximize lH (Ψ( X ))-| M |, or if Ψ is given, to minimize the number | M | of disclosed bits. Characteristics of reconciliation protocols Before dealing with the details of reconciliation, let us here review some of its characteristics. First, reconciliation can be either one-way or interactive . The first case is obviously only possible with one-way secret-key distillation, as information is sent only from Claude to Dominique.
Some QKD protocols, as I will detail in Chapter 11, produce Gaussian key elements. The reconciliation methods of the previous chapter are, as such, not adapted to this case. In this chapter, we build upon the previous techniques to treat the case of continuous-variable key elements or, more generally, the case of non-binary key elements. In the first two sections, I describe two techniques to process non-binary key elements, namely sliced error correction and multistage soft decoding. Then, I conclude the chapter by giving more specific details on the reconciliation of Gaussian key elements. Sliced error correction Sliced error correction (SEC) is a generic reconciliation protocol that corrects strings of non-binary elements using binary reconciliation protocols as primitives [173]. The purpose of sliced error correction is to start from a list of correlated values and to give, with high probability, equal binary strings to Claude and Dominique. The underlying idea is to convert Claude's and Dominique's values into strings of bits, to apply a binary correction protocol (BCP) on each of them and to take advantage of all available information to minimize the number of exchanged reconciliation messages. It enables Claude and Dominique to reconcile a wide variety of correlated variables X and Y while relying on BCPs that are optimized to correct errors modeled by a binary symmetric channel (BSC). An important application of sliced error correction is to correct correlated Gaussian random variables, namely X ∼ N (0, Σ) and Y = X + ∈ with ∈ ∼ N (0, σ). This important particular case is needed for QKD protocols that use a Gaussian modulation of Gaussian states, as described in Chapter 11.
Secret-key distillation (SKD) is the technique used to convert some given random variables, shared among the legitimate parties and a potential eavesdropper Eve, into a secret key. Secret-key distillation is generally described as a protocol between the legitimate parties, who exchange messages over the public classical authenticated channel as a function of their key elements X and Y , aiming to agree on a common secret key K . We assume here that the eavesdropper's knowledge can be modeled as a classical random variable. For more general assumptions on the eavesdropping techniques, please refer to Chapter 12. The quantum transmission is assumed to be from Alice to Bob. In order to be able to specify another direction for secret-key distillation, we use the Claude-and-Dominique naming convention. Here, the random variables X and Y model the variables obtained by Claude and Dominique, respectively, using the quantum channel, and the random variable Z contains anything that Eve was able to infer from eavesdropping on the quantum channel. As detailed in Section 11.3.2, both assignments (Alice = Claude ∧ Bob = Dominique) and (Alice = Dominique ∧ Bob = Claude) are useful. In this chapter, I first propose a general description of the reconciliation and privacy amplification approach. I then list the different characteristics that a SKD protocol can have. And finally, I overview several important classes of known results and treat the specific case of SKD with continuous variables.
We study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret X of min-entropy k, and wish to agree on secret key R of length m over a public communication channel completely controlled by a computationally unbounded attacker Eve. Despite being extensively studied in the literature, the problem of designing “optimal ” efficient privacy amplification protocols is still open, because there are several optimization goals. The first of them is (1) minimizing the entropy loss L = k−m (it is known that the optimal value for L = O(λ), where ε = 2−λ is the desired security of the protocol). Other important considerations include (2) minimizing the number of communication rounds, (3) maintaining security even after the secret key is used (this is called post-application robustness), and (4) ensuring that the protocol P does not leak some “useful information ” about the source X (this is called source privacy). Additionally, when dealing with a very long source X, as happens in the so-called Bounded Retrieval Model (BRM), extracting as long a key as possible is no longer the goal. Instead, the goals are (5) to touch as little of X as possible (for efficiency), and (6) to be able to run the protocol many times on the same X, extracting multiple secure keys.
In this chapter, I will discuss some important aspects of universal families of hash functions. I will not remain completely general, however, as we are only interested in universal families of hash functions for the purpose of privacy amplification of QKD-produced bits. In the first section, I explain my motivations, detailing the requirements for families of hash functions in the scope of privacy amplification. I then give some definitions of families and show how they fit our needs. Finally, I discuss their implementation. Defined in Section 6.3.1, the essential property of an ∈/| B |-almost universal family of hash function is recalled in Fig. 7.1. Requirements For the purpose of privacy amplification, families of hash functions should meet some important requirements. They are listed below: The family should be universal (∈ = 1) or very close to it (∈ ≈ 1). The number of bits necessary to represent a particular hash function within its family should be reasonably low. The family should have large input and large output sizes. The evaluation of a hash function within the family should be efficient. The first requirement directly affects the quality of the produced secret key. The closer to universality, the better the secrecy of the resulting key – see Section 6.3.1. The second requirement results from the fact that the hash function will be chosen randomly within its family and such a choice has to be transmitted between Claude and Dominique. It is not critical, however, because the choice of the hash function need not be secret. A number of bits proportional to the input size is acceptable.
Privacy Amplification, introduced by Bennett et. al in [1] and generalized in [2], is the technique of shrinking a partially secret string to a highly secret one by public discussion. More precisely, in the privacy amplification phase, two legitimate parties, Alice and Bob, who share a partially secret string S about an opponent Eve has partial information to extract, and a shorter but highly-secret string S' by communication through an public channel such that Eve’s information about S' is negligible, i.e., ε= ≥ −S' U uH ( / ) log S2 | '| holds with very high probability for some small ε > 0, where the random variable U summarizes Eve’s complete knowledge about S', and u is the particular value known to Eve [2]. Privacy amplification is an important step in both quantum cryptography and key theoretically secret information agreement [3].
Two parties, Alice and Bob, wish to distill a binary secret key out of a list of correlated variables that they share after running a quantum key distribution (QKD) protocol based on continuous-spectrum quantum carriers. We present a novel construction that allows the legitimate parties to get equal bit strings out of correlated variables by using a classical channel, with as little leaked information as possible. This opens the way to securely correcting nonbinary key elements. In particular, the construction is refined to the case of Gaussian variables as it applies directly to recent continuous-variable protocols for QKD.