{'fraction_non_alphanumeric': 0.0487399528615459, 'fraction_numerical': 0.01066658608811265, 'mean_word_length': 3.9197264753976513, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Leftover Hashing Against Quantum Side Information

The Leftover Hash Lemma states that the output of a two-universal hash function applied to an input with sufficiently high entropy is almost uniformly random. In its standard formulation, the lemma refers to a notion of randomness that is (usually implicitly) defined with respect to classical side information. Here, we prove a (strictly) more general version of the Leftover Hash Lemma that is valid even if side information is represented by the state of a quantum system. Furthermore, our result applies to arbitrary delta-almost two-universal families of hash functions. The generalized Leftover Hash Lemma has applications in cryptography, e.g., for key agreement in the presence of an adversary who is not restricted to classical information processing.


I. INTRODUCTION
We will first consider the task of extracting uniform randomness from a random variable and introduce the Leftover Hash Lemma. Following its discussion, we extend the scenario to include side information that is potentially stored in a quantum state.

A. Randomness Extraction
Consider a random variable X that is partially known to an agent, i.e., the agent possesses side information E correlated to X. One may ask whether it is possible to extract from X a part Z that is completely unknown to the agent, i.e., uniform conditioned on E. If yes, what is the maximum size of Z? And how is Z computed?
The Leftover Hash Lemma answers these questions. It states that extraction of uniform randomness Z is possible whenever the agent's uncertainty about X is sufficiently large. More precisely, the number ℓ of extractable bits is approximately equal to the min-entropy of X conditioned on E, denoted H min (X|E) (see Section I B for a definition and properties). Furthermore, Z can be computed as the output of a function f selected at random from a suitably chosen family of functions F , called twouniversal family of hash functions (see Section I C for a definition). Remarkably, the family F can be chosen without knowing the actual probability distribution of X and only depends on the alphabet X of X and the number of bits ℓ to be extracted. The lemma immediately implies that for a fixed joint distribution of X and E, there is a fixed function f that extracts almost uniform randomness. More precisely, given any ∆ > 0, there exists a function f that produces ℓ = H min (X|E) − 2 log 1 2∆ (1) bits that are ∆-close to uniform and independent of E. 2 The Leftover Hash Lemma plays an important role in a variety of applications in computer science and cryptography (see, e.g., [1] for an overview). A prominent example is privacy amplification, i.e., the task of transforming a weakly secret key (over which an adversary may have partial knowledge E), into a highly secret key (that is uniform and independent of the adversary's information E). It was in this context that the use of two-universal hashing for randomness distillation has first been proposed [2]. Originally, the analysis was however restricted to situations where X is uniform and E is bounded in size. Later, versions of the Leftover Hash Lemma similar to Lemma 1 above have been proved independently in [3] and [4]. The term leftover hashing was coined in [5], where its use for recycling the randomness in randomized algorithms and for the construction of pseudo-random number generators is discussed (see also [3,6]). 1 The distance from uniform ∆ measures the statistical distance of the probability distribution of X given E to a uniform distribution. See Section III for a formal definition. 2 We use log to denote the binary logarithm.

B. Quantum Side Information
A majority of the original work on universal hashing is based entirely on probability theory and side information is therefore (often implicitly) assumed to be represented by a classical system E (modeled as a random variable). 3 In fact, since hashing is an entirely "classical" process (a simple mapping from a random variable X to another random variable Z), one may expect that the physical nature of the side information is irrelevant and that a purely classical treatment is sufficient. This is, however, not necessarily the case. It has been shown, for instance, that the output of certain extractor functions may be partially known if side information about their input is stored in a quantum device of a certain size, while the same output is almost uniform conditioned on any side information stored in a classical system of the same size (see [7] for a concrete example and [8] for a more general discussion). 4 Here, we follow a line of research started in [9][10][11] and study randomness extraction in the presence of quantum side information E (which, of course, includes situations where E is partially or fully classical.) More specifically, our goal is to establish a generalized version of Lemma 1 which holds if the system E is quantum-mechanical. For this, we first need to quickly review the notion of minentropy as well as of the notion of uniformity, which need to be extended accordingly.
The definition of uniformity in the context of quantum side information E is rather straightforward. Let Z be a classical random variable which takes any value z ∈ Z with probability p z and let E be a quantum system whose state conditioned on Z = z is given by a density operator ρ on H E . This situation is compactly described by the classical-quantum (CQ) state defined on the product space H Z ⊗ H E , where H Z is a Hilbert space with orthonormal basis {|z Z } z∈Z . We say that Z is uniform conditioned on E if ρ ZE has product form ω Z ⊗ρ E , where ω Z := 1 Z /|Z| is the maximally mixed state on H Z . More generally, we say that Z is ∆-close to uniform conditioned on E if there exists a state σ E on E for which the trace distance between ρ ZE and ω Z ⊗ σ E is 3 If the side information E is classical, the Leftover Hash Lemma can be formulated without the need to introduce E explicitly (see, e.g., [3]). Instead, one may simply interpret all probability distributions as being conditioned on a fixed value of the side information. 4 Note that there is no sensible notion of a conditional probability distribution where the conditioning is on the state of a quantum (as opposed to a classical ) system. An implicit treatment of side information E, where one considers all probability distributions to be conditioned on a specific value of E, as explained in the previous footnote, is therefore not possible in the general case.
at most ∆ (see Section III for a formal definition). The trace distance is a natural choice of metric because it corresponds to the distinguishing advantage. 5 Furthermore, in the purely classical case, the trace distance reduces to the statistical distance. Next, we generalize the notion of min-entropy to situations involving quantum side information. Before we do this, note that the classical min-entropy H min (X|E) has an operational interpretation as the guessing probability of X given E, namely Here, p guess (X|E) denotes the probability of correctly guessing the value of X using the optimal strategy with access to E. The optimal strategy in the classical case is to guess, for each value of e of E, the X with the highest conditional probability P X|E=e . The guessing probability is thus A generalization of the min-entropy to situations where E may be a quantum system has first been proposed in [10] (see Section II for a formal definition). As shown in [13], the operational interpretation (3) naturally extends to this more general case. In other words, the min-entropy, H min (X|E), is a measure for the probability of guessing X using an optimal strategy with access to the quantum system E. However, the actual requirement on the entropy measure used in Lemma 1 is that it accurately characterizes the total amount of randomness contained in X, i.e. the number of uniformly random bits that can be extracted using an optimal extraction strategy. As we will show below, H min (X|E) (or, more precisely, a smooth version of it) meets this requirement.
For this purpose, let ρ XE be fixed and assume that f is a function that maps X to a string Z = f (X) ∈ {0, 1} ℓ of length ℓ that is uniform conditioned on the side information E. Then, obviously, the probability of guessing Z correctly given E is equal to 2 −ℓ and, by virtue of (3), we find that Furthermore, the probability of guessing Z = f (X) correctly cannot be smaller than the probability of guessing X, correctly. This fact can again be expressed in terms of min-entropies, 5 Let psucc be the maximum probability that a distinguisher, presented with a random choice of either the state ρ or the state σ, can correctly guess which of the two he has seen. The distinguishing advantage is then defined as the advantage compared to a random guess, which is given by psucc − 1 2 = 1 4 ρ − σ 1 (see e.g. [12]) i.e., the min-entropy can only decrease under the action of a function. Combining (4) and (5) immediately yields We conclude that the number ℓ of uniform bits (relative to E) that can be extracted from data X is upper bounded by the min-entropy of X conditioned on E. This result may be seen as a converse of (1). So far, the claim (6) is restricted to the extraction of perfectly uniform randomness. In order to extend this concept to the more general case of approximately uniform randomness, we need to introduce the notion of smooth min-entropy. Roughly speaking, for any ε ≥ 0, the ε-smooth min-entropy of X given E, denoted H ε min (X|E), is defined as the maximum value of H min (X|E) evaluated for all density operatorsρ that are ε-close to ρ (see Section II for a formal definition).
The above argument leading to (6) can be generalized in a straightforward manner to smooth min-entropy, and results in the bound ℓ ≤ H 2 √ ∆ min (X|E) for the maximum number ℓ of extractable bits that are ∆-close to uniform conditioned on E. Crucially, our extended version of the Leftover Hash Lemma implies that this bound can be reached, up to additive terms of order log(1/∆) (see Theorem 6 and Theorem 7). We thus conclude that the min-entropy of X conditioned on E, in particular its "smoothed" version, is an accurate measure for the amount of uniform randomness (conditioned on E) that can be extracted from X.

C. Almost Two-Universal Hashing
The notion of two-universal hashing has been introduced by Carter and Wegman [14]. A family F of functions from X to Z is said to be two-universal if, for any pair of distinct inputs x and x ′ , and for f chosen at random from F , the probability of a collision f (x) = f (x ′ ) is not larger than δ := 1/|Z|. Note that this value for the collision probability corresponds to the one obtained by choosing F as the family of all functions with domain X and range Z.
Later, the concept of two-universal hashing has been generalized to arbitrary collision probabilities δ [15]. Namely, a family of functions F from X to Z is called for any x = x ′ . A two-universal family as above simply corresponds to the special case δ = 1/|Z|. The classical Leftover Hash Lemma (Lemma 1) can be generalized to δ-almost two-universal hash functions [1]. More precisely, when extracting an ℓ-bit string from data X, its distance from uniform conditioned on E is bounded by ∆ = 1 2 (2 ℓ δ − 1) + 2 ℓ−Hmin(X|E) .

D. Main result
Our main result is a generalization of the Leftover Hash Lemma for δ-almost two-universal families of hash functions which is valid in the presence of quantum side information. While the statement is new for general δ-almost two-universal hash functions, the special case where δ = 2 −ℓ has been proved previously by one of us [10].
Lemma 2 (General Leftover Hash Lemma). Let X be a random variable, let E be a quantum system, and let F be a δ-almost two-universal family of hash functions from X to {0, 1} ℓ . Then, on average over the choices of Note that inserting δ = 2 −ℓ into the first expression for ∆ yields a formula which is less tight than (8). The latter, therefore, requires a separate proof. In the technical part below, the two claims are formulated more generally for the smooth min-entropy (Theorem 6 and Theorem 7).

E. Applications and Related Work
Quantum versions of the Leftover Hash Lemma [10] for two-universal families of hash functions have been used in the context of privacy amplification against a quantum adversary [8,11]. This application has gained prominence with the rise of quantum cryptography and quantum key distribution in particular. There, the side information E is gathered during a key agreement process between two parties by an eavesdropper who is not necessarily limited to classical information processing. The quantum generalization of the Leftover Hash Lemma is then used to bound the amount of secret key that can be distilled by the two parties.
The restriction to two-universal families of hash functions leads to the need for a random seed of length Θ(n), where n is the length in bits of the original partially secret string. This seed is used to choose f from a two-universal family F . The main result of this paper, Lemma 2, and a suitable construction of a δ-almost two-universal family of hash functions (see Section IV) allow for a shorter seed of length proportional to ℓ, log n ℓ and log 1 ∆ . The length of secret key that can be extracted with this method is only reduced by a term proportional to log 1 ∆ compared to the extractor using two-universal hashing. Furthermore, the generalized Leftover Hashing Lemma allows for an extension of existing cryptographic security proofs to δ-almost two-universal families of hash functions and may lead to a speed-up in practical implementations. 6 Recently, the problem of randomness extraction with quantum side information has generated renewed interest. It has been shown that the classical technique [18] of XORing a classical source about which an adversary holds quantum information with a δ-biased mask results in a uniformly distributed string [19] 7 .
However, to achieve even shorter seed lengths, more advanced techniques such as Trevisan's [21] extractor have been studied in [22][23][24]. In [23], it is shown that a seed of length O(polylog n) is sufficient to generate a key of length ℓ ≈ H min (X) − log dim H E , where dim H E is a measure of the size of the adversary's quantum memory. In [24], the result was extended to the formalism of conditional min-entropies. They attain a key length of ℓ ≈ H ε min (X|E), which can be arbitrarily larger than H min (X) − log dim H E . Furthermore, as we show in (6), this key length is almost optimal. Our result may be useful to further improve the performance of these extractors (see discussion in [24]).
Furthermore, our result should be used instead of the classical Leftover Hashing Lemma whenever randomness is extracted in a context governed by the laws of quantum physics. For example, consider a device that needs a seed that is random conditioned on its internal state. In this case the use of the classical Leftover Hashing Lemma instead of its quantum version, Lemma 2, corresponds to the implicit and potentially unjustified assumption that the device does not make use of quantum mechanics.

F. Organization of the paper
In Section II, we discuss various aspects of the smooth entropy framework, which will be needed for our proof. We then give the proof of our generalized Leftover Hash Lemma (Lemma 2) in Section III. More precisely, we provide statements of the Leftover Hashing Lemma for twouniversal and δ-almost two-universal hashing in terms of the smooth min-entropy (Theorems 9 and 10). Finally, in Section IV, we combine known constructions of δ-almost two-universal hash functions and discuss their use for randomness extraction with shorter random seeds. Appendix B may be of independent interest because it establishes a relation between the smooth min-and maxentropies (as defined above and used in [13,25,26]) and certain related entropic quantities used in earlier work (e.g., in [10])

II. SMOOTH ENTROPIES
Let H be a finite-dimensional Hilbert space. We use L(H), L † (H) and P(H) to denote the set of linear, Hermitian and positive semi-definite operators on H, respectively. We define the set of normalized quantum states by S = (H) := {ρ ∈ P(H) : tr ρ = 1} and the set of subnormalized states by S ≤ (H) := {ρ ∈ P(H) : 0 < tr ρ ≤ 1}. Given a pure state |φ ∈ H, we use φ = |φ φ| to denote the corresponding projector in P(H). The inverse of a Hermitian operator is meant to be taken on its support only (generalized inverse). Given a bipartite Hilbert space H AB := H A ⊗ H B and a state ρ AB ∈ S ≤ (H AB ), we denote by ρ A and ρ B its marginals ρ A = tr B ρ AB and The trace distance between states ρ and τ is given by We also employ the purified distance P as a metric on S ≤ (H) [26]. It is an upper bound on the trace distance and defined in terms of the generalized fidelityF as We will need that the purified distance is a monotone under trace non-increasing completely positive maps (CPMs). Let E be a trace non-increasing CPM, then [26] Note that the projections ρ → ΠρΠ for any projector Π is a trace non-increasing CPM. We define the ε-ball of states close to ρ ∈ S ≤ (H) as We will now define the smooth min-entropy [10].
Definition 1. Let ε ≥ 0 and ρ AB ∈ S ≤ (H AB ). The minentropy of A conditioned on B is given by Furthermore, the smooth min-entropy of A conditioned on B is defined as The conditional min-entropy is a measure of the uncertainty about the state of a system A given quantum side information B. In particular, if the system A describes a classical random variable (i.e. if the state is CQ), the minentropy can be interpreted as a guessing probability. 8 For general quantum states, the smooth min-entropy satisfies data-processing inequalities. For example, if a CPM is applied to the B system or if a measurement is conducted on the A system, the smooth min-entropy of A given B is guaranteed not to decrease. 9 Finally, we will need a fully quantum generalization of the collision entropy (Rényi-entropy of order 2). Definition 2. Let ρ AB ∈ S ≤ (H AB ) and σ B ∈ P(H B ), then the collision entropy of A conditioned on B of a state ρ AB given We will use the fact that the collision entropy provides an upper bound on the min-entropy. The proof of the following statement can be found in Appendix C and constitutes one of the main technical contributions of this work.

III. PROOF OF THE LEFTOVER HASH LEMMA
In this section we give bounds on the distance from uniform of the quantum state after privacy amplification with two-universal and δ-almost two-universal hashing (Theorems 6 and 7). The proof of Lemma 2 then follows.
First, we extend the definition of the distance from uniform to sub-normalized states for technical reasons. 10 Definition 3. Let ρ AB ∈ S ≤ (H AE ), then we define the distance from uniform of A conditioned on B as ∆(A|B) ρ := min where ω A := 1 A / dim H A and the minimum is taken over all σ B ∈ P(H B ) satisfying tr σ B = tr ρ B .
As a first step, we bound the distance from uniform in terms of the collision entropy.
9 See [26] for precise statements and proofs. 10 Note that sub-normalized states have to be considered due to our definition of the smoothing of the min-entropy.
Proof. We apply the Hölder inequality (Lemma 18 in Appendix A) with parameters r = t = 4, s = 2, . This leads to We simplify the expression on the r.h.s. further using which concludes the proof.
The above bound can be simplified by setting τ B = ρ B : We now consider a scenario where X is picked from a set X and E is a quantum system whose state may depend on X. The situation is described by a CQ-state of the form where the probability of x occurring is the trace of the sub-normalized state ρ E . After applying a function f : X → {0, 1} ×ℓ chosen at random from a family of hash functions F , the resulting CQ-state is given by where z ∈ {0, 1} ×ℓ , p f = 1/|F | and Formally, randomness extraction can be modelled as a trace-preserving CPM, A, from H FX → H FZ that maps The followoing lemma yields a bound on the collision entropy of the output of the hash function in terms of the collision entropy of the input.
Lemma 5. Let F be δ-almost two-universal, let ρ XE and ρ FZE be defined as in (14) and (15), respectively, and let τ E ∈ S = (H E ). Then, We now complete the second sum with the terms where x = x ′ to get the statement of the lemma.
If we set τ E = ρ E , the result can be simplified further: We are now ready to give a bound on the distance from uniform ∆(Z|F E) after privacy amplification with two-universal and δ-almost two-universal families of hash functions. Note that we consider the distance from uniform conditioned on F as well as E. This describes the situation where the chosen hash function (the value f ) is published after its use (strong extractor regime).
The distance from uniform conditioned on E averaged over the choice of f is given by and it can be bounded in terms of ∆(Z|F E) as where σ E optimizes (12) for ∆(Z|EF ) ρ . Hence, an upper bound on ∆(Z|F E) implies an upper bound on the average distance to uniform conditioned on E as well.
For two-universal hashing, we get the following bound (see also [10]). Theorem 6. Let F be two-universal and let ρ XE and ρ ZEF be defined as in (14) and (15), respectively. Then, for any ε ≥ 0, Proof. We use Lemma 4 to bound ∆(Z|F E) ρ . In particular, we set τ FE := ρ F ⊗ τ E to get where we have used Lemma 5 and that F is two-universal (δ ≤ 2 −ℓ ) in the last step. The r.h.s. can be expressed in terms of a min-entropy using (10). With an appropriate choice of τ E , we have We have now shown the statement of the theorem for the case ε = 0. Finally, the bound can be expressed in terms of a smooth min-entropy. Letρ XE ∈ B ε (ρ XE ) be the CQstate (cf. Lemma 19) that optimizes the smooth minentropy H ε min (X|E) ρ = H min (X|E)ρ. We defineρ FZE := (A ⊗ I E )(ρ F ⊗ρ XE ) and note that privacy amplification can only decrease the purified distance (9), i.e.
Moreover, letσ FE be the state that minimizes the distance from uniform d u (Z|F E)ρ. Then, We now apply (19) forρ FZE (instead of ρ FZE ) to get which concludes the proof.
Next, we consider the case of δ-almost two-universal hashing.
Theorem 7. Let F be δ-almost two-universal and let ρ XE and ρ ZEF be defined as in (14) and (15), respectively. Then, for any ε ≥ 0 andε > 0, Proof. We use Lemma 4 as in (13) to bound ∆(Z|F E) ρ . For normalized ρ ZFE , we find where we used Lemma 5 as stated in (17). The smoothing of the above equation is achieved using the same arguments as in the proof of Theorem 9. However, this time we need to include an additional smoothing parameterε > 0 in order to be able to apply (11).
Following the arguments laid out in the proof of Theorem 6, we have This can be bounded using (20), which concludes the proof.
The proof of the Leftover Hash Lemma stated in the introduction (Lemma 2) follows when we set ε = 0 in Theorem 9 and Theorem 10. To see this, note that the statements of two theorems can be expressed in terms of the distance from uniform averaged over the choice of f using (18).

IV. EXPLICIT CONSTRUCTIONS WITH SHORTER SEEDS
Here, we combine known constructions of twouniversal and δ-almost two-universal hash functions and discuss their use for randomness extraction with shorter random seeds. We consider a scenario where X is an nbit string x ∈ {0, 1} ×n and E is a quantum system. The challenge is typically to optimize the following parameters: a) the error described by the distance from uniform, e := ∆(Z|F E), which should be small, b) the length of the extracted key, ℓ, which one wants to make as large as possible (close to H ε min (X|E)) and c) the length of the random seed, s := log |F |, needed to choose f , which one wants to keep small.
The latter point is important in practical implementations of privacy amplification, for example in quantum key distribution (QKD), where the choice of f has to be communicated between two parties. We will first review the explicit constructions of (δalmost) two-universal hash functions used in this section. In [14], Carter and Wegman proposed several constructions of two-universal function families, trying to minimize the size of F . An example of a two-universal set of hash functions with |F | = 2 n is the set F = {f α } α∈{0,1} n consisting of elements where x·α denotes the multiplication in the field GF(2 n ). The fact that F is two-universal can be readily verified by considering the difference With δ-almost two-universal families, a larger value of δ typically allows for a smaller set F . This is nicely illustrated by the following well-known construction based on polynomials. Let F be an arbitrary field and let r be a positive integer. We define the family F = {f α } α∈F of functions Using the fact that a polynomial of degree r − 1 can only have r − 1 zeros, it is easy to verify that F is δ-almost two-universal, for δ = (r − 1)/|F|.
Combining the general results on δ-almost twouniversal hashing of Section III with the explicit constructions described above, we obtain the following statements.
If we do not care about s, we may choose a twouniversal family of hash functions and recover a result by Renner [10]: Proof. We apply Theorem 6 using the two-universal family constructed in (21), which yields s = log |F | = n.
We now show that we can choose a family of hash functions such that s is proportional to the key length ℓ instead of the input string length n.
Proof. We use the standard classical way of concatenating two hash functions to obtain the required parameters [27]. For the first function, we set k = ⌊ℓ + log(n/ℓ) + log(1/ε 2 )⌋ and use the field F = GF(2 k ) in the polynomial-based hash construction from (22). Interpreting the n-bit strings as r = ⌈n/k⌉ blocks of k bits, the first hash function maps from {0, 1} ×n to {0, 1} ×k and requires a k-bit seed. Then, regular two-universal hashing from (21) with a seed length of again k bits is used to map from {0, 1} ×k to {0, 1} ×ℓ . The two seed lengths add up to s = 2k = 2⌊ℓ + log(n/ℓ) + log(1/ε 2 )⌋. Polynomial-based hashing achieves a δ 1 of at most by the choice of r and the fact that k ≥ ℓ + log(n/ℓ) + log(1/ε 2 ) − 2. Together with the δ 2 ≤ 2 −ℓ from the twouniversal hashing, we get from Lemma 8 that this construction yields a δ 1 + δ 2 ≤ 1+4ε 2 2 ℓ -almost two-universal family of hash functions. Inserting this expression for δ into Theorem 7 and settingε = ε yields The theorem then follows as an upper bound to this expression.
Corollary 13. Let ρ ∈ S ≤ (H) and ϕ ∈ H ⊗ H ′ be a purification of ρ. Then, and equality holds if the Hilbert space dimensions satisfy dim H ′ ≥ dim H.
The following lemma establishes a fundamental property of pure bipartite states, namely that every linear operator applied to one subsystem has a dual on the other subsystem, such that the resulting pure state is the same.
Lemma 14. Let φ AB ∈ P(H AB ) be pure, ρ A = tr B φ AB , ρ B = tr A φ AB and let X ∈ L(H A ) be an operator with support and image in supp {ρ A }. Then, where the transpose is taken with regard to the Schmidt basis of φ AB .

Proof. We introduce the Schmidt decomposition |φ AB
|γ AB is the (unnormalized) fully entangled state on the support of ρ A and ρ B . It is easy to verify that (X ⊗ 1 B )|γ AB = (1 A ⊗ X T )|γ AB , where the transposed matrix is given by Corollary 15. Let φ AB ∈ P(H AB ) be pure, ρ A = tr B φ AB , ρ B = tr A φ AB and f : R + → R a real-valued function, then We define the notion of a dual projector with regard to a pure state using the following corollary: The next Lemma gives a bound on the purified distance of a state ρ and a projected state ΠρΠ.
without increasing the distance. Lemma 17. Let ρ ∈ S ≤ (H) and Π a projector on H, then Proof. The generalized fidelity between the two states can be bounded using tr(Πρ) ≤ tr(ρ). We havē The desired bound on the purified distance follows from its definition.
We also need a Hölder inequality for linear operators and unitarily invariant norms (see [29] for a proof). Here, we state a version for three operators and the trace norm: Lemma 18. Let A, B and C be linear operators and r, s, t > 0 such that 1 r + 1 s + 1 t = 1, then The following lemma makes clear that the min-entropy smoothing of a state will not destroy its CQ structure.
Proof. Letρ AB be any state in B ε (ρ XB ). We can establish a CQ-stateρ XB by measuring A in the basis determined by X. This operation will not increase the distance P (ρ AB , ρ XB ) (cf. [26], Lemma 7) and not decrease the min-entropy (cf. [26], Theorem 19). Thus, we can conclude that the optimal state is CQ.
where the infimum is taken over all embeddings ρ AB' of ρ AB into H A ⊗ H B' . In fact, it is sufficient to consider an embedding into a space of size dim H B' = rank {ρ AB } · dim H A . The first definition of the smooth max-entropy, H ε max (A|B), is used in [13,25] and is found to have many interesting properties, e.g. it satisfies a data-processing inequality [26]. The alternative definition, H ε max (A|B), was first introduced in [10] and is used to quantitatively characterize various information theoretic tasks (cf. e.g. [31,33,34]). Here, we find that the two smooth minentropies and the two smooth max-entropies are pairwise equivalent up to terms in log ε. Namely, the following lemma holds: The equivalence of the max-entropies follows by their definition as duals, i.e. we have For convenience of exposition, we introduce the generalized conditional min-entropy The proof of Lemma 20 is based on the following result.
Lemma 21. Let ε > 0 and ρ ABC ∈ S ≤ (H ABC ) be pure. Then, there exists a projector Π AC on H AC and a statẽ ρ ABC = Π AC ρ ABC Π AC such thatρ ABC ∈ B ε p (ρ ABC ) and Furthermore, there exists a stateρ AB ∈ S ≤ (H AB ) that satisfiesρ AB ∈ B ε (ρ AB ) and Proof. The proof is structured as follows: First, we give a lower bound on the entropy h min (A|B)ρ |ρ in terms of H min (A|B) ρ and a projector Π B that is the dual projector (cf. Corollay 16) of Π AC with regard to ρ ABC . We then find a lower bound on the purified distance between ρ ABC andρ ABC in terms of Π B and define Π B (and, thus, Π AC ) such that this distance does not exceed ε.
Let λ and σ B be the pair that optimizes the minentropy H min (A|B) ρ , i.e. H min (A|B) ρ = h min (A|B) ρ|σ = − log λ. We haveρ B ≤ ρ B by definition ofρ ABC . Hence, h min (A|B)ρ |ρ is finite and can be written as where ||X|| ∞ denotes the maximum eigenvalue of X. We bound this expression using the dual projector Π B of Π AC with regard to ρ ABC and the fact that ρ AB ≤ λ1 A ⊗ σ B by definition of λ and σ B : where, in the last step, we introduced the Hermitian operator Γ B := ρ Taking the logarithm on both sides leads to We use Lemma 17 to bound the distance between ρ ABC andρ ABC , namely , where the last equality can be verified using Corollary 16. Clearly, the optimal choice of Π B will cut off the largest eigenvalues of Γ B in (B5) while keeping the states ρ ABC andρ ABC close. We thus define P B to be the minimum rank projector onto the smallest eigenvalues of Γ B such that tr(Π B ρ B ) ≥ tr ρ B −ε 2 /2 or, equivalently, tr(Π ⊥ B ρ B ) ≤ ε 2 /2. This definition immediately implies that ρ ABC and ρ ABC are ε-close and it remains to find an upper bound Let Π ′ B be the projector onto the largest remaining eigenvalue in Π B Γ B Π B and note that Π ′ B and Π ⊥ B commute with Γ B . Then, where µ B is minimized over all positive operators in the support of Π ⊥ In the last step we used that tr(ρ 1 /2 We have now established the first statement. To prove the second statement, we introduce an operator ∆ B := ρ B −ρ B ≥ 0. The stateρ AB =ρ AB +1 A /d A ⊗∆ B , where d A = dim H A , satisfiesρ B = ρ B . We now show that the stateρ AB is ε-close to ρ AB . The inequalityρ AB ≤ρ AB implies || √ρ AB √ ρ AB || 1 ≤ || √ρ AB √ ρ AB || 1 and, thus, F (ρ AB ,ρ AB ) ≥ F (ρ AB , ρ AB ) + 1 − tr ρ AB ≥ F (ρ ABC , ρ ABC ) + 1 − tr ρ AB where we used the monotonicity of the fidelity F (ρ, τ ) := || √ ρ √ τ || 1 under the partial trace. Thus, P (ρ AB , ρ AB ) ≤ ε.
We use thatρ B = ρ B andρ AB ≤ρ AB + 1 A /d A ⊗ ρ B to find a lower bound on H min (A|B)ρ = h min (A|B)ρ |ρ : We have λ ≥ tr ρ AB /d A (Lemma 20 in [26]) and, thus, This concludes the proof of the second statement.

Appendix C: Collision Entropy
In this section, we prove Lemma 3, which gives a relation between the collision entropy and the min-entropy. First, we provide an inequality in terms of relative entropies.
Using the above result and Lemma 21 of Appendix B, we are ready to prove Lemma 3 of Section II.
Proof of Lemma 3. To prove the first statement, we apply Lemma 23 to the state ρ XB . The inequality holds in particular for the state σ B that optimizes H min (X|B) ρ (cf. Definition 4), establishing (10).
Next, we use Lemma 21 to defineρ XB ∈ Bε(ρ XB ). Thus, In particular, we can chooseρ XB normalized and CQ. 12 We apply Lemma 23 to this state to get which concludes the proof of (11).