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.
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.
This paper examines classical privacy amplification using a universal family of hash functions. In quantum key distribution, the adversary's measurement can wait until the choice of hash functions is announced, and so the adversary's information may depend on the choice. Therefore the existing result on classical privacy amplification, which assumes the independence of the choice from the other random variables, is not applicable to this case. This paper provides a security proof of privacy amplification which is valid even when the adversary's information may depend on the choice of hash functions. The compression rate of the proposed privacy amplification can be taken to be the same as that of the existing one with an exponentially small loss in secrecy of a final key.
Quantum Key Distribution (QKD) protocols typically involve two separate steps of error-verification and privacy amplification. Both steps involve the application of a hash function sampled from a suitable hash family to classical data. A potentially simpler alternative is to implement a single-step hashing procedure, announce and compare a fixed number of bits of its output for error-verification, and retain the remaining bits as the final output key. This reduces the complexity of classical postprocessing, the amount of classical communication, and the amount of randomness needed in the protocol. While this construction has appeared in the literature, a suitable mathematical justification is lacking. In this work, we show that the security of such protocols, under certain simple conditions, follows from a slightly modified notion of secrecy of the protocol without the final error-verification step. In particular, we show that for most entropy-based proofs, the combined protocol can be implemented with no change to the key rate, and a minor change to the security parameter.
In this paper, we introduce the concept of dual universality of hash functions and present its applications to quantum cryptography. We begin by establishing the one-to-one correspondence between a linear function familyFand a code familyC, and thereby defining ε-almost dual universal2hash functions, as a generalization of the conventional universal2hash functions. Then, we show that this generalized (and thus broader) class of hash functions is in fact sufficient for the security of quantum cryptography. This result can be explained in two different formalisms. First, by noting its relation to the δ-biased family introduced by Dodis and Smith, we demonstrate that Renner's two-universal hashing lemma is generalized to our class of hash functions. Next, we prove that the proof technique by Shor and Preskill can be applied to quantum key distribution (QKD) systems that use our generalized class of hash functions for privacy amplification. While Shor-Preskill formalism requires an implementer of a QKD system to explicitly construct a linear code of the Calderbank-Shor-Steane (CSS) type, this result removes the existing difficulty of the construction of a linear code of CSS code by replacing it by the combination of an ordinary classical error correcting code and our proposed hash function. We also show that a similar result applies to the quantum wire-tap channel. Finally, we compare our results in the two formalisms and show that, in typical QKD scenarios, the Shor-Preskill-type argument gives better security bounds in terms of the trace distance and Holevo information than the method based on the δ-biased family.
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.
We explicitly construct random hash functions for privacy amplification (extractors) that require smaller random seed lengths than the previous literature, and still allow efficient implementations with complexity O(n log n) for input length n. Firstly, we construct two types of hash functions by using the finite-filed. Then, concatenating them, we construct other two types of hash functions. We compare our hash functions with existing hash function in an asymptotic setting under a fixed key generation rate.
In this section, I wish to put quantum key distribution (QKD) in the wider context of a cryptosystem. I shall discuss informally some aspects that are considered important. The questions I wish to answer here are: “What are the ingredients needed to make a QKD-based cryptosystem work? What services does it bring? What are its limitations?” As I shall detail below, QKD may be used to provide the users with confidential communications. This can be achieved when we combine QKD and the one-time pad. For the quantum modulation, QKD needs a source of truly random numbers. Also, QKD requires a classical authenticated channel to work, so authentication plays an essential role. As a consequence, QKD must start with a secret key, making it a secret-key encryption scheme. I will also discuss what happens if classical cryptography is introduced in the system. Finally, I will describe the implementation of a simple cryptosystem on top of QKD. A key distribution scheme The first function of QKD is to distribute a secret key between two parties. The use of this key is outside the scope of this first section – the need for a secret key is omnipresent in cryptography. As depicted in Fig. 5.1, QKD relies on a classical authenticated channel for sifting and secret-key distillation and on random bits for the modulation of quantum states. The key produced by QKD can be intended for encryption purposes – this will be discussed in Section 5.2 – but is also required by authentication. A part of the distributed key is used for authentication. When QKD is run for the first time, however, an initial secret key must be used instead.