A Quantum-Proof Non-malleable Extractor

Abstract

In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret X in order to establish a shared private key K by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantum-proof extractor allows one to establish security against quantum adversaries.

In the case that the channel is not authenticated, this simple solution is no longer secure. Nevertheless, Dodis and Wichs (STOC’09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor.

We give the first construction of a non-malleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS’12), and is able to extract from source of min-entropy rates larger than 1 / 2. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, due to Cohen and Vidick (unpublished) we obtain the first privacy amplification protocol secure against active quantum adversaries.

D. Aggarwal—This research was further partially funded by the Singapore Ministry of Education and the National Research Foundation under grant R-710-000-012-135.

K.-M. Chung—This research is partially supported by the 2016 Academia Sinica Career Development Award under Grant no. 23-17, and MOST QC project under Grant no. MOST 107-2627-E-002-002.

H.-H. Lin—This material is based on work supported by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13.

T. Vidick—Supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028).

1 Introduction

Privacy amplification. We study the problem of privacy amplification [4, 5, 30, 31] (PA). In this problem, two parties, Alice and Bob, share a weak secret X (a random variable with min-entropy at least k). Using X and an insecure communication channel, Alice and Bob would like to securely agree on a secret key R that is $\epsilon$-close to uniformly random even to an adversary Eve who may have full control over their communication channel. This elegant problem has multiple applications including biometric authentication, leakage-resilient cryptography, and quantum cryptography.

If the adversary Eve is passive, i.e., she is only able to observe the communication but may not alter the messages exchanged, then there is a direct solution based on the use of a strong seeded randomness extractor $\mathrm {Ext}$ [33]. This can be done by Alice selecting a uniform seed Y for the extractor, and sending the seed to Bob; Alice and Bob both compute the key $R = \mathrm {Ext}(X, Y)$, which is close to being uniformly random and independent of Y by the strong extractor property. The use of a quantum-proof extractor suffices to protect against adversaries holding quantum side information about the secret X.

Privacy amplification is substantially more challenging when the adversary is active, i.e. Eve can not only read but also modify messages exchanged across the communication channel. This problem has been studied extensively in several works including [2, 3, 8, 9, 12, 13, 16, 17, 19, 20, 25,26,27,28,29, 31, 35], yielding constructions that are optimal or near-optimal in any of the parameters involved in the problem, including the min-entropy k, the error $\epsilon$, and the communication complexity of the protocol.

Active adversaries with quantum side information. We consider the problem of active attacks by quantum adversaries. This question arises naturally when privacy amplification is used as a sub-protocol, e.g., as a post-processing step in quantum key distribution (QKD), when it may not be safe to assume that the classical communication channel is authenticated.¹ To the best of our knowledge the question was first raised in [7], whose primary focus is privacy amplification with an additional property of source privacy. Although the authors of [7] initially claimed that their construction is secure against quantum side information, they later realized that there was an issue with their argument, and withdrew their claim of quantum security. The only other work we are aware of approaching the question of privacy amplification in the presence of active quantum adversaries is [14]. In this paper it is shown that a classical protocol for PA introduced by Dodis and Wichs [19] remains secure against active quantum attacks when the main tool used in the protocol, a non-malleable extractor, is secure against quantum side information (a notion that is also formally introduced in that paper, and to which we return shortly). Unfortunately, the final contribution of [14], a construction of a quantum-proof non-malleable extractor, also had a flaw in the proof, invalidating the construction. Thus, the problem of quantum-secure active privacy amplification remained open.

It may be useful to discuss the difficulty faced by both these previous works, as it informed our own construction. The issue is related to the modeling of the side information held by the adversary Eve, and how that side information evolves as messages are being exchanged, and possibly modified, throughout the privacy amplification protocol. To explain this, consider the setting for a non-malleable extractor, whose security property can be defined without referring to the way the extractor is used for privacy amplification. Here, Alice initially has a secret X (the source), while Eve holds side information E, a quantum state, correlated with X. Alice selects a uniformly random seed Y and computes $\mathrm {Ext}(X,Y)$. However, in addition to receiving Y (as would already be the case for a strong randomness extractor), Eve is also given the possibility to select an arbitrary $Y'\ne Y$ and receive $\mathrm {Ext}(X,Y')$ as “advice” to help her break the extractor—i.e., distinguish $\mathrm {Ext}(X,Y)$ from uniform. Now, clearly in any practical scenario the adversary may use her side information E in order to guide her choice of $Y'$; thus $Y'$ should be considered as the outcome of a measurement $\{M_y^{y'}\}$, depending on $Y=y$ and performed on E, which returns an outcome $Y'=y'$ and a post-measurement state $E'$. This means that the security of the extractor should be considered with respect to the side information $E'$. But due to the measurement, $E'$ may be correlated with both X and Y in a way that cannot be addressed by standard techniques for the analysis of strong extractors. Indeed, even if $E'$ is classical, so that we can condition on its value, X and Y may not be independent after conditioning on $E' = e'$; due to the lack of independence it is unclear whether extraction works. (Classical proofs condition on $E=e$ at the outset, which does preserve independence.)

The issue seems particularly difficult to accommodate when analyzing extractors based on the technique of “alternate extraction”, as was attempted in [7, 14]. In fact, in the original version of [7] the issue is overlooked, resulting in a flawed security proof. In [14] the authors attempted to deal with the difficulty by using the formalism of quantum Markov chains; unfortunately, there is a gap in the argument and it does not seem like the scenario can be modeled using the Markov chain formalism. Note that in the classical setting the issue does not arise: having fixed $E=e$ we can consider $Y'$ to be a fixed, deterministic function of Y—there is no $E'$ to consider, and X is independent of both Y and $Y'$ conditioned on $E=e$. In this paper we do not address the issue, but instead focus on a specific construction of non-malleable extractor whose security can be shown by algebraic techniques sidestepping the difficulty; we explain our approach in more detail below.

Our results. We show that a non-malleable extractor introduced by Li [27] in the classical setting is secure against quantum side information. Combining this construction with the protocol of Dodis and Wichs and its proof of security from [14], we obtain the first protocol for privacy amplification that is secure against active quantum adversaries.

Before describing our results in more detail we summarize Li’s construction and its analysis for the case of classical side information. The construction is based on the inner product function. Let p be a prime, $\mathbb {F}_p$ the finite field with p elements, and $\langle \cdot , \cdot \rangle$ the inner product over $\mathbb {F}_p$. Consider the function $\mathrm {Ext}: \mathbb {F}_p^n \times \mathbb {F}_p^n \rightarrow \mathbb {F}_p$ given by $\mathrm {Ext}(X, Y) := \langle X, Y \rangle$, where $X \in \mathbb {F}_p^n$ is a weak secret with min-entropy (conditioned on the adversary’s side information) assumed to be greater than $(n \log p)/2$, and Y is a uniformly random and independent seed. For this function to be a non-malleable extractor, it is required that $\mathrm {Ext}(X, Y)$ is close to uniform and independent of $\mathrm {Ext}(X, f(Y))$, where f is any adversarially chosen function such that $f(Y) \ne Y$ for all Y. This is clearly not true, since if $f(Y) = cY$ for some $c \in \mathbb {F}_p\setminus \{1\}$, then $\mathrm {Ext}(X, f(Y)) = c \mathrm {Ext}(X, Y)$, and hence we don’t get the desired independence. Thus, for such a construction to work, it is necessary to encode the source Y as ${\mathsf {Enc}}(Y)$, for a well-chosen function ${\mathsf {Enc}}$, in such a way that $\langle X, {\mathsf {Enc}}(Y) \rangle - c\cdot \langle X, {\mathsf {Enc}}(f(Y))\rangle$ is hard to guess. The non-uniform XOR lemma [3, 13, 17] shows that it is sufficient to show that $\langle X, {\mathsf {Enc}}(Y) \rangle - c\cdot \langle X, {\mathsf {Enc}}(f(Y))\rangle = \langle X, {\mathsf {Enc}}(Y) - c\cdot {\mathsf {Enc}}(f(Y)) \rangle$ is close to uniform conditioned on Y and E. The encoding that we use in this paper (which is almost the same as the encoding chosen by Li) is to take $Y \in \mathbb {F}_{p}^{n/2}$, and encode it as $Y \Vert Y^2$, which we view as an n-character string over $\mathbb {F}_p$, with the symbol $\Vert$ denoting concatenation of strings and the square taken by first interpreting Y as an element of $\mathbb {F}_{p^{n/2}}$. Then it is not difficult to show that for any function f such that $f(Y) \ne Y$ and any c, we have that $(Y\Vert Y^2) - (c \cdot f(Y) \Vert c\cdot f(Y)^2)$ (taking the addition coordinatewise) has min-entropy almost $(n\log p)/2$. Thus, provided X has sufficiently high min-entropy and using the fact that X and $(Y\Vert Y^2) - (c \cdot f(Y) \Vert c\cdot f(Y)^2)$ are independent conditioned on E, the strong extractor property of the inner product function gives the desired result.²

Our main technical result is a proof of security of Li’s extractor, against quantum side information. We show the following (we refer to Definition 5 for the formal definition of a quantum-proof non-malleable extractor):

Theorem 1

Let $p\ne 2$ be a prime. Let n be an even integer. Then for any $\epsilon >0$ the function $\mathrm {nmExt}(X,Y):\mathbb {F}_p^n \times \mathbb {F}_p^{n/2} \rightarrow \mathbb {F}_p$ given by $\langle X, Y\Vert Y^2 \rangle$ is an $(\left(\frac{n}{2}+6\right){\log p} -1+4\log \frac{1}{\epsilon },\epsilon )$ quantum-proof non-malleable extractor.

We give the main ideas behind our proof of security for this construction, highlighting the points of departure from the classical analysis. Subsequently, we explain the application to privacy amplification.

Proof ideas. We begin by generalizing the first step of Li’s argument, the reduction provided by the non-uniform XOR lemma, to the quantum case. An XOR lemma with quantum side information is already shown in [22], where the lemma is used to show security of the inner product function as a two-source extractor against quantum side information. This version is not sufficient for our purposes, and we establish the following generalization, which may be of independent interest (we refer to Sect. 3 for relevant definitions):

Lemma 1

Let p be a prime power and t an integer. Let $\rho _{X_0XE}$ be a ccq state with $X_0 \in \mathbb {F}_p$ and $X=(X_1,\dots ,X_t)\in \mathbb {F}^t_p$. For all $a=(a_1,\dots ,a_t)\in \mathbb {F}^t_p$, define a random variable $Z=X_0+\langle a,X\rangle =X_0+\sum _{i=1}^t a_i X_i$. Let $\epsilon \ge 0$ be such that for all a, $\frac{1}{2}\left\Vert \rho ^a_{ZE}-U_Z\otimes \rho _E \right\Vert_1\le \epsilon$. Then

$$\begin{aligned} \frac{1}{2}\big \Vert \rho _{X_0XE}-U_{X_0}\otimes \rho _{XE}\big \Vert _1&\le p^{\frac{t+1}{2}} \sqrt{\frac{\epsilon }{2}}\;. \end{aligned}$$

(1.1)

XOR lemmas are typically proved via Fourier-based techniques (including the one in [22]). Here we instead rely on a collision probability-based argument inspired from [3]. We prove Lemma 1 by observing that such arguments generalize to the quantum setting, as in the proof of the quantum leftover hash lemma in [36].

Based on the XOR lemma (used with $t=1$), following Li’s arguments it remains to show that the random variable $\langle X,g(Y,Y')\rangle \in \mathbb {F}_p$, where $g(Y,Y') = Y\Vert Y^2 - c(Y'\Vert Y'^2) \in \mathbb {F}_p^n$, is close to uniformly distributed from the adversary’s point of view, specified by side information $E'$, for every $c \ne 0 \in \mathbb {F}_p$. As already mentioned earlier, this cannot be shown by a reduction to the security proof of the inner product function as a two-source extractor against side information, as X and $g(Y,Y')$ are not independent (not even conditioned on the value of $E'$ when $E'$ is classical).

Instead, we are led to a more direct analysis which proceeds by formulating the problem as a communication task.³ We relate the task of breaking our construction—distinguishing $\langle X,g(Y,Y')\rangle$ from uniform—to success in the following task. Alice is given access to a random variable X, and Bob is given a uniformly random Y. Alice is allowed to send a quantum message E, correlated with X, to Bob. Bob then selects a $Y' \ne Y$ and returns a value $b\in \mathbb {F}_p$. The players win if $b=\langle X,g(Y,Y')\rangle$. Based on our previous reductions it suffices to show that no strategy can succeed with probability substantially higher than random in this game, unless Alice’s initial message to Bob contains a large amount of information about X; more precisely, unless the min-entropy of X, conditioned on E, is less than half the length of X.

Note that the problem as we formulated it does not fall in standard frameworks for communication complexity. In particular, it is a relation problem, as Bob is allowed to choose the value $Y'$ to which his prediction b applies. This seems to prevent us from using any prior results on the communication complexity of the inner product function, and we develop an ad-hoc proof which may be of independent interest. We approach the problem using the “reconstruction paradigm” (used in e.g. [15]), which amounts to showing that from any successful strategy of the players one may construct a measurement for Bob which completely “reconstructs” X, given E; if this can be achieved with high enough probability it will contradict the min-entropy assumption on X, via its dual formulation as a guessing probability [23]. We show this by running Bob’s strategy “in superposition”, and applying a Fourier transform to recover a guess for X. This argument is similar to one introduced in [11, 32]. We refer to Sect. 4.1 for more detail.

Application to privacy amplification. Finally we discuss the application of our quantum-proof non-malleable extractor to the problem of privacy amplification against active quantum attacks, which is our original motivation. The application is based on a breakthrough result by Dodis and Wichs [19], who were first to show the existence of a two-round PA protocol with optimal (up to constant factors) entropy loss $L = \Theta ({\log (1/\epsilon )})$, for any initial min-entropy k. This was achieved by defining and showing the existence of non-malleable extractors with very good parameters.

The protocol from [19] is recalled in Sect. 5. The protocol proceeds as follows. Alice sends a uniformly random seed Y to Bob over the communication channel, which is controlled by Eve. Bob receives a possibly modified seed $Y'$. Then Alice computes a key $K = \mathrm {nmExt}(X, Y)$, and Bob computes $K' = \mathrm {nmExt}(X, Y')$. In the second round, Bob generates another uniformly random seed $W'$, and sends $W'$ together with $T' = \textsc {MAC}_{K'}(W')$ to Alice, where $\textsc {MAC}$ is a one-time message authentication code. Alice receives a possibly modified T, W and checks whether $T = \textsc {MAC}_K(W)$. If yes, then the shared secret between Alice and Bob is $\mathrm {Ext}(X, W) = \mathrm {Ext}(X, W')$ with overwhelming probability, where $\mathrm {Ext}$ is any strong seeded extractor.

The security of this protocol intuitively follows from the following simple observation. If the adversary does not modify Y, then $K' = K$, and so $W'$ must be equal to W by the security of the $\textsc {MAC}$. If $Y' \ne Y$, then by the non-malleability property of $\mathrm {nmExt}$, K is uniform and independent of $K'$, and so it is impossible for the adversary to predict $\textsc {MAC}_K(W)$ for any W even given $K'$ and $W'$.

Since [19] could not construct an explicit non-malleable extractor, they instead defined and constructed a so called a look-ahead extractor, which can be seen as a weakening of the non-malleability requirement of a non-malleable extractor. This was done by using the alternating extraction protocol by Dziembowski and Pietrzak [18].

In [14], Dodis and Wichs’ reduction is extended to the case of quantum side information, provided that the non-malleable Extractor $\mathrm {nmExt}$ used in the protocol satisfies the appropriate definition of quantum non-malleability, and $\mathrm {Ext}$ is a strong quantum-proof extractor. Based on our construction of a quantum-proof non-malleable extractor (Theorem 1) we immediately obtain a PA protocol that is secure as long as the initial secret X has a min-entropy rate of (slightly more than) half. The result is formalized as Corollary 1 in Sect. 5.

In Sect. 5.2 we additionally prove security of a one-round protocol due to Dodis et al. [16] against active quantum attacks. The protocol has the advantage of being single-round, but it induces a significantly higher entropy loss, $(n/2) + \log (1/\epsilon )$, than the Dodis-Wichs protocol, for which the loss is independent of n.

Future work. There have been a series of works in the classical setting [3, 9, 12, 13, 17, 20, 25, 27,28,29] that have given privacy amplification protocols (via constructing non-malleable extractors or otherwise) that achieve near-optimal parameters. In particular, Li [29] constructed a non-malleable extractor that works for min-entropy $k = \Omega (\log n + {\log (1/\epsilon )}\log {\log (1/\epsilon )})$, where $\epsilon$ is the error probability.

Our quantum-proof non-malleable extractor requires the min-entropy rate of the initial weak secret to be larger than 1 / 2. We leave it as an open question whether one of the above-mentioned protocols that work for min-entropy rate smaller than 1 / 2 in the classical setting can be shown secure against quantum side information.

2 Preliminaries

2.1 Notation

For p a prime power we let $\mathbb {F}_p$ denote the finite field with p elements. For any positive integer n, there is a natural bijection $\phi : \mathbb {F}_p^n \mapsto \mathbb {F}_{p^n}$ that preserves group addition and scalar multiplication, i.e., the following hold:

• For all $c \in \mathbb {F}_p$, and for all $x \in \mathbb {F}_p^n$, $\phi (c \cdot x) = c \cdot \phi (x)$.

• For all $x_1, x_2 \in \mathbb {F}_p^n$, $\phi (x_1) + \phi (x_2) = \phi (x_1 + x_2)$.

We use this bijection to define the square of an element in $\mathbb {F}_p^n$, e.g. for $y \in \mathbb {F}_p^n$

$$\begin{aligned} y^2=\phi ^{-1}\left((\phi (y))^2\right)\;. \end{aligned}$$

(2.1)

We write $\langle \cdot ,\cdot \rangle$ for the inner product over $\mathbb {F}_p^n$. $\log$ denotes the logarithm with base 2.

We write $\mathcal {H}$ for an arbitrary finite-dimensional Hilbert space, $\mathrm {L}(\mathcal {H})$ for the linear operators on $\mathcal {H}$, $\mathrm {Pos}(\mathcal {H})$ for positive semidefinite operators, and $\mathrm {D}(\mathcal {H})\subset \mathrm {Pos}(\mathcal {H})$ for positive semidefinite operators of trace 1 (density matrices). A linear map $T:\mathrm {L}(\mathcal {H})\rightarrow \mathrm {L}(\mathcal {H}')$ is CPTP if it is completely positive, i.e. $T\otimes \mathop {\mathrm {Id}}\nolimits (A)\ge 0$ for any $d\ge 0$ and $A\in \mathrm {Pos}(\mathcal {H}\otimes \mathbb {C}^d)$, and trace-preserving.

We use capital letters $A,B,E,X,Y,Z,\ldots$ to denote quantum or classical random variables. Generally, the letters near the beginning of the alphabet, such as A, B, E, represent quantum variables (density matrices on a finite-dimensional Hilbert space), while the letters near the end, such as X, Y, Z represent classical variables (ranging over a finite alphabet). We sometimes represent classical random variables as density matrices diagonal in the computational basis, and write e.g. $(A ,B , \dots , E )_\rho$ for the density matrix $\rho _{A ,B, \dots , E}$. For a quantum random variable A, we denote $\mathcal {H}_{A}$ the Hilbert space on which the associated density matrix $\rho _A$ is supported, and $d_A$ its dimension. If X is classical we loosely identify its range $\{0,\ldots ,d_X-1\}$ with the space $\mathcal {H}_X$ spanned by $\{{\left| {0}\right\rangle }_X,\ldots ,{\left| {d_X-1}\right\rangle }_X\}$. We denote $I_A$ the identity operator on $\mathcal {H}_A$. When an identity operator is tensor producted with another matrix, we sometimes omit the identity operator for brevity, e.g. writing $I_A \otimes B$ as B. When a density matrix specifies the states of two random variables, one of which is classical and the other is quantum, we call it a classical-quantum(cq)-state. A cq state $(X,E)_\rho$ takes the form

$$\begin{aligned}&\rho _{XE}=\sum _x |x\rangle \langle x|_X\otimes \rho ^x_E\;, \end{aligned}$$

where the summation is over all x in the range of X and $\{\rho ^x_E\}$ are positive semidefinite matrices with ${{\,\mathrm{\text{ Tr }}\,}}\rho _E^x=p_x$, where $p_x$ is the probability of getting the outcome x when measuring the X register. Similarly, a ccq state $(X,Y,E)_\sigma$ is a density matrix over two classical variables and one quantum variable, e.g. $\sigma _{XYE}=\sum _{x,y} |x\rangle \langle x|_X\otimes |y\rangle \langle y|_Y\otimes \sigma ^{xy}_E$. We will sometimes add or remove random variables from an already-specified density matrix. When we omit a random variable, we mean the reduced density matrix, e.g. $(Y,E)_\sigma = {{\,\mathrm{\text{ Tr }}\,}}_X( \sigma _{XYE})$. When we introduce a classical variable, we mean that the classical variable is computed into another classical register. For example, for a function $F(\cdot ,\cdot )$ on variables X, Y,

$$\begin{aligned} (F(X,Y),X,Y,E)_\sigma = \sum _{f,x,y} {\delta }({f,F(x,y)}) |f\rangle \langle f|\otimes |x\rangle \langle x|\otimes |y\rangle \langle y|\otimes \sigma ^{xy}_E\;, \end{aligned}$$

where ${\delta }(\cdot ,\cdot )$ is the Kronecker delta function, and the summation over f is taken over the range of F. When F is a random function, the density matrix is averaged over the appropriate probability distribution.

We use $U_\Sigma$ to denote the uniform distribution over a set $\Sigma$. For m-bit string $\{0,1\}^m$, we abbreviate $U_{\{0,1\}^m}$ as $U_m$. For a classical random variable X, $U_X$ denote the uniform distribution over the range of X.

For $p\ge 1$ we write $\left\Vert \cdot \right\Vert_p$ for the Schatten p-norm (this is the p-norm of the vector of singular values). We write $\left\Vert \cdot \right\Vert$ for the operator norm.

We write $\approx _\epsilon$ to denote that two density matrices are $\epsilon$-close to each other in trace distance. For example, $(X,E)_\rho \approx _\epsilon (U_X,E)_\rho$ means $\frac{1}{2}\left\Vert \rho _{XE}- U_X \otimes \rho _{E} \right\Vert_1 \le \epsilon$. Note that in case both X and E are classical random variables, this reduces to the statistical distance.

2.2 Quantum Information

The min-entropy of a classical random variable X conditioned on quantum side information E is defined as follows.

Definition 1

(Min-entropy). Let $\rho _{XE} \in \mathrm {D}(\mathcal {H}_X \otimes \mathcal {H}_E)$ be a cq state. The min-entropy of X conditioned on E is defined as

$$\begin{aligned} H_{\mathrm {min}}({X|E})_\rho = \max \{\lambda \ge 0 : \exists \sigma _E \in \mathrm {Pos}(\mathcal {H}_E), {{\,\mathrm{\text{ Tr }}\,}}\left(\sigma _E \right)\le 1, \, \mathrm {s.t.}\,\, 2^{-\lambda } I_X \otimes \sigma _E \ge \rho _{XE}\}. \end{aligned}$$

When the state $\rho$ with respect to which the entropy is measured is clear from context we simply write $H_{\mathrm {min}}({X|E})$ for $H_{\mathrm {min}}({X|E})_\rho$.

Definition 2

((n, k) -source). A cq state $\rho _{XE}$ is an (n, k)-source if $n= \log d_X$ and $H_{\mathrm {min}}({X|E}))_\rho \ge k$.

Rather than using Definition 1, we will most often rely on an operational expression for the min-entropy stated in the following lemma from [23].

Lemma 2

(Min-entropy and guessing probability). For a cq state $\rho _{XE}\in \mathrm {D}(\mathcal {H}_X\otimes \mathcal {H}_E)$, the guessing probability is defined as the probability to correctly guess X with the optimal strategy to measure E, i.e.

$$\begin{aligned} p_{guess}(X|E)_\rho = \sup _{\{M_x\}}\sum _x p_x {{\,\mathrm{\text{ Tr }}\,}}\left( M_x \rho ^x_E\right)\;, \end{aligned}$$

(2.2)

where ${\{M_x\}}$ is a positive operator-valued measure (POVM) on $\mathcal {H}_E$. Then the guessing probability is related to the min-entropy by

$$\begin{aligned} p_{guess}(X|E)_\rho = 2^{-H_{\mathrm {min}}(X|E)_\rho }\;. \end{aligned}$$

(2.3)

2.3 Extractors

We first give the definition of a strong quantum-proof extractor. Recall the notation $(X,E)_\rho \approx _\epsilon (X',E')_\rho$ for $\frac{1}{2}\Vert \rho _{XE}-\rho _{X'E'}\Vert _1 \le \epsilon$, and $U_m$ for a random variable uniformly distributed over m-bit strings.

Definition 3

Let k be an integer and $\epsilon \ge 0$. A function $\mathrm {Ext}: \mathcal {H}_X \times \mathcal {H}_Y \rightarrow \mathcal {H}_Z$ is a strong $(k,\epsilon )$ quantum-proof extractor if for all cq states $\rho _{XE}\in \mathrm {D}(\mathcal {H}_X\otimes \mathcal {H}_E)$ with $H_{\mathrm {min}}(X|E) \ge k$, and for a classical uniform $Y\in \mathcal {H}_Y$ independent of $\rho _{XE}$,

$$ (\mathrm {Ext}(X,Y),Y,E)_\rho \approx _\epsilon (U_Z,Y,E)_\rho \;.$$

There are known explicit constructions of strong quantum-proof extractors.

Theorem 2

([36]). For any integers $d_X,k$ and for any $\epsilon > 0$ there exists an explicit strong $(k,\epsilon )$ quantum-proof extractor $\mathrm {Ext}:\{0,\ldots ,d_X-1\} \times \{0,\ldots ,d_Y-1\} \rightarrow \{0,\ldots ,d_Z-1\}$ with $\log d_Y = O(\log d_X)$ and $\log d_z = k-O(\log (1/\epsilon ))-O(1)$.

We use the same definition of non-malleable extractor against quantum side information that was introduced in the work [14]. The definition is a direct generalization of the classical notion of non-malleable extractor introduced in [19]. The first step is to extend the notion that the adversary may query the extractor on any different seed $Y'$ than the seed Y actually used to the case where $Y'$ may be generated from Y as well as quantum side information held by the adversary.

Definition 4

(Map with no fixed points). Let $\mathcal {H}_Y$, $\mathcal {H}_E$ and $\mathcal {H}_{E'}$ be finite-dimensional Hilbert spaces. We say that a CPTP map $T:\mathrm {L}(\mathcal {H}_Y\otimes \mathcal {H}_E)\rightarrow \mathrm {L}(\mathcal {H}_Y\otimes \mathcal {H}_{E'})$ has no fixed points if for all $\rho _E\in \mathrm {D}(\mathcal {H}_E)$ and all computational basis states ${\left| {y}\right\rangle }\in \mathcal {H}_Y$ it holds that

$$ {\left\langle {y}\right| }_Y \,\text{ Tr }_{\mathcal {H}_{E'}}\big ( T\big (|y\rangle \langle y|_Y\otimes \rho _E\big )\big )\,{\left| {y}\right\rangle }_Y\, =\, 0\;.$$

The following definition is given in [14]:

Definition 5

(Non-malleable extractor). Let $\mathcal {H}_X$, $\mathcal {H}_Y$, $\mathcal {H}_Z$ be finite-dimensional Hilbert spaces, of respective dimension $d_X$, $d_Y$, and $d_Z$. Let $k\le \log d_X$ and $\epsilon >0$. A function

$$\mathrm {nmExt}\,:\, \{0,\ldots ,d_X-1\}\times \{0,\ldots ,d_Y-1\} \rightarrow \{0,\ldots ,d_Z-1\}$$

is a $(k,\epsilon )$ quantum-proof non-malleable extractor if for every cq-state $(X,E)_\rho$ on $\mathcal {H}_X \otimes \mathcal {H}_E$ such that $H_{\mathrm {min}}(X|E)_\rho \ge k$ and any CPTP map $\mathrm {Adv}: \mathrm {L}(\mathcal {H}_Y\otimes \mathcal {H}_E) \rightarrow \mathrm {L}(\mathcal {H}_Y \otimes \mathcal {H}_{E'})$ with no fixed points,

$$ \big \Vert \sigma _{\mathrm {nmExt}(X,Y) \mathrm {nmExt}(X,Y') YY' E'} - U_Z \otimes \sigma _{\mathrm {nmExt}(X,Y') YY'E'}\big )\big \Vert _1 \le \epsilon \;,$$

where

$$\begin{aligned} \sigma _{YY'XE'} \,=\, \frac{1}{d_Y}\sum _{y} |y\rangle \langle y|_Y \otimes (I_X \otimes \mathrm {Adv})( |y\rangle \langle y|_Y \otimes \rho _{XE} ) \end{aligned}$$

(2.4)

and $\sigma _{\mathrm {nmExt}(X,Y) \mathrm {nmExt}(X,Y') YY' E'}$ is obtained from $\sigma _{YY'XE'}$ by (classically) computing $\mathrm {nmExt}(X,Y)$ and $\mathrm {nmExt}(X,Y')$ in ancilla registers and tracing out X.

2.4 Hölder’s Inequality

We use the following Hölder’s inequality for matrices. For a proof, see e.g. [6].

Lemma 3

(Hölder’s inequality). For any $n\times n$ matrices A, B, C with complex entries, and real numbers $r,s,t > 0$ satisfying $\frac{1}{r}+\frac{1}{s}+\frac{1}{t}=1$,

$$\begin{aligned} \left\Vert ABC \right\Vert_1 \le \left\Vert |A|^r \right\Vert_1^{1/r} \left\Vert |B|^s \right\Vert_1^{1/s} \left\Vert |C|^t \right\Vert_1^{1/t} \;. \end{aligned}$$

(2.5)

3 Quantum XOR Lemma

In this section we prove two XOR lemmas with quantum side information. We prove a non-uniform version, Lemma 1, in Sect. 3.1. In the full version of the paper [1], we also prove a more standard XOR lemma with quantum side information for completeness.⁴ Since XOR lemmas often play a fundamental role, they might be of independent interest. Our proofs are based on quantum collision probability techniques⁵ from [36] to transform a classical collision probability-based proof into one that also allows for quantum side information. The idea of non-uniform XOR lemma is natural in the context of non-malleable extractors, and has been explored in [3, 13, 27]. Our non-uniform XOR lemma generalizes a restricted version of Lemma 3.15 of [27] to $\mathbb {F}_p$ with quantum side information.⁶

The quantum collision probability is defined as follows.

Definition 6

(Quantum collision probability). Let $\rho _{AB} \in \mathrm {D}(\mathcal {H}_A\otimes \mathcal {H}_B)$ and $\sigma _B \in \mathrm {D}(\mathcal {H}_B)$. The collision probability of $\rho _{AB}$, conditioned on $\sigma _B$, is defined as

$$\begin{aligned} \Gamma _c(\rho _{AB}|\sigma _B) \equiv {{\,\mathrm{\text{ Tr }}\,}}\left(\rho _{AB} (I_A\otimes \sigma _B^{-1/2}) \right)^2 \;,\end{aligned}$$

(3.1)

where $\sigma _B \in \mathrm {D}(\mathcal {H}_B)$.

A careful reader might notice that $\Gamma _c \le 1$ is not generally true, so calling $\Gamma _c$ collision probability seems misleading. We give a general definition which allows arbitrary states $\rho _{AB}$ and $\sigma _B$ to match the existing literature, but here we always consider cq states $\rho _{AB}$ and take $\sigma _B=\rho _B$. We prove in the full version [1] that $\Gamma _c \le 1$ in such cases. $\Gamma _c(\rho _{AB}|\sigma _B)$ also reduces to the classical collision probability when both of A, B are classical and $\sigma _B=\rho _B$.

We will often use the following relation, also taken from [36], valid for any $\rho _{AB} \in \mathrm {D}(\mathcal {H}_A\otimes \mathcal {H}_B)$:

$$\begin{aligned} {{\,\mathrm{\text{ Tr }}\,}}\left((\rho _{AB}-U_A \otimes \rho _B )(I_A\otimes \rho _B^{-1/2})\right)^2 \,=\,\Gamma _c\big (\rho _{AB}|\rho _B\big ) - \frac{1}{d_A}\;, \end{aligned}$$

(3.2)

which can be verified by expanding the square:

$$\begin{aligned}&{{\,\mathrm{\text{ Tr }}\,}}\Big ((\rho _{AB}-U_A \otimes \rho _B )(I_A\otimes \rho _B^{-1/2})\Big )^2 \\&= {{\,\mathrm{\text{ Tr }}\,}}\left(\rho _{AB} \, \rho _B^{-1/2}\right)^2 - 2 {{\,\mathrm{\text{ Tr }}\,}}\left(\rho _{AB} \, \rho _B^{-1/2} (U_A \rho _B) \rho _B^{-1/2}\right) +{{\,\mathrm{\text{ Tr }}\,}}\left((U_A \rho _B) \rho _B^{-1/2}\right)^2 \\&=\Gamma _c(\rho _{AB}|\rho _B) - \frac{1}{d_A}\;. \end{aligned}$$

3.1 Non-uniform XOR Lemma

Our non-uniform XOR lemma bounds the distance to uniform of a ccq state, a state with two classical registers and one quantum register. Roughly speaking, the lemma states that given two random variables $X_0 \in \mathbb {F}_p$ and $X \in \mathbb {F}_p^t$, if $X_0+\langle a,X\rangle$ is close to uniform, then $X_0$ is close to uniform given X.

Lemma 1 (restated). Let p be a prime power, t an integer and $\epsilon \ge 0$. Let $\rho _{X_0XE}$ be a ccq state with $X_0 \in \mathbb {F}_p$ and $X=(X_1,\dots ,X_t)\in \mathbb {F}^t_p$. For all $a=(a_1,\dots ,a_t)\in \mathbb {F}^t_p$, define a random variable $Z=X_0+\langle a,X\rangle =X_0+\sum _{i=1}^t a_i X_i$. If for all a, $\frac{1}{2}\left\Vert \rho ^a_{ZE}-U_Z\otimes \rho _E \right\Vert_1\le \epsilon$, then

$$\begin{aligned} \frac{1}{2}\big \Vert \rho _{X_0XE}-U_{X_0}\otimes \rho _{XE}\big \Vert _1&\le \frac{p^{(t+1)/2}}{\sqrt{2}}\sqrt{\epsilon } \;. \end{aligned}$$

(3.3)

The proof of the non-uniform XOR lemma has the following structure: we bound the collision probability by the trace distance in Lemma 5, then prove the non-uniform XOR lemma based on that. First we establish that for any ccq state $\rho _{XZE}$:

$$\begin{aligned}&{{\,\mathrm{\text{ Tr }}\,}}\left((\rho _{XZE}-U_X \otimes \rho _{ZE} )(I_{XZ}\otimes \rho _E^{-1/2})\right)^2 \nonumber \\&= {{\,\mathrm{\text{ Tr }}\,}}\left(\rho _{XZE} \, \rho _E^{-1/2}\right)^2 - 2 {{\,\mathrm{\text{ Tr }}\,}}\left(\rho _{XZE} \, \rho _E^{-1/2} (U_X \rho _{ZE}) \rho _E^{-1/2}\right) +{{\,\mathrm{\text{ Tr }}\,}}\left((U_X \rho _{ZE}) \rho _E^{-1/2}\right)^2 \nonumber \\&=\Gamma _c(\rho _{XZE}|\rho _E) - \frac{1}{d_X}\Gamma _c(\rho _{ZE}|\rho _E)\;. \end{aligned}$$

(3.4)

We need the following lemma to bound the collision probability by the trace distance in Lemma 5.

Lemma 4

Let $\rho _{XZE}$ be a ccq state. Then

$$\begin{aligned} -\frac{1}{d_X}I_{XZE}\le&\left(I_{XZ}\otimes \rho _E^{-\frac{1}{2}}\right)(\rho _{XZE}-U_X \otimes \rho _{ZE} )\left(I_{XZ}\otimes \rho _E^{-\frac{1}{2}}\right) \le \left(1-\frac{1}{d_X}\right) I_{XZE}\;. \end{aligned}$$

(3.5)

Proof

We bound the eigenvalues of the middle expression. Since $\rho _{XZE}$ is a ccq state, we know that the middle expression

$$\begin{aligned}&\left(I_{XZ}\otimes \rho _E^{-1/2}\right)(\rho _{XZE}-U_X \otimes \rho _{ZE} )\left(I_{XZ}\otimes \rho _E^{-1/2}\right) \nonumber \\&=\sum _{x,z} |x\rangle \langle x|\otimes |z\rangle \langle z|\otimes \rho _E^{-1/2} \left(\rho ^{xz}_E- \frac{1}{d_X} \rho ^z_E \right)\rho _E^{-1/2} \end{aligned}$$

(3.6)

is block diagonal, where $\rho ^z_E=\sum _x\rho ^{xz}_E$ and $\rho _E=\sum _{x,z}\rho ^{xz}_E$. For any state ${\left| {\phi }\right\rangle }\in \mathcal {H}_E$ and x, z in the range of X, Z,

$$\begin{aligned} \langle \phi |\rho _E^{-1/2} \left(\rho ^{xz}_E- \frac{1}{d_X} \rho ^z_E \right)\rho _E^{-1/2}|\phi \rangle \ge \langle \phi |\rho _E^{-1/2} \left(- \frac{1}{d_X} \rho ^z_E \right)\rho _E^{-1/2}|\phi \rangle \ge -\frac{1}{d_X}\;. \end{aligned}$$

(3.7)

This proves the first inequality. We also have

$$\begin{aligned}&\langle \phi |\rho _E^{-1/2} \left(\rho ^{xz}_E- \frac{1}{d_X} \rho ^z_E \right)\rho _E^{-1/2}|\phi \rangle \nonumber \\&=\langle \phi |\rho _E^{-1/2} \left(\rho ^{xz}_E- \frac{1}{d_X} \sum _{x'} \rho ^{x'z}_E \right)\rho _E^{-1/2}|\phi \rangle \nonumber \\&=\left(1- \frac{1}{d_X}\right) \langle \phi |\rho _E^{-1/2} \rho ^{xz}_E \rho _E^{-1/2}|\phi \rangle -\frac{1}{d_X} \sum _{x'\ne x} \langle \phi |\rho _E^{-1/2} \rho ^{xz}_E \rho _E^{-1/2}|\phi \rangle \nonumber \\&\le \left(1- \frac{1}{d_X}\right) \;. \end{aligned}$$

(3.8)

This proves the second inequality.

We then bound the collision probability by the trace distance.

Lemma 5 (Bounding collision probability with trace distance, non-uniform)

Let $\rho _{XZE}$ be a ccq state. If

$$\begin{aligned} \frac{1}{2}\left\Vert \rho _{XZE}-U_X \rho _{ZE} \right\Vert_1=\epsilon \,, \end{aligned}$$

(3.9)

then

$$\begin{aligned} \frac{4 \epsilon ^2 }{d_X d_Z} \le \Gamma _c(\rho _{XZE}|\rho _E) - \frac{1}{d_X}\Gamma _c(\rho _{ZE}|\rho _E) \le 2 \epsilon \left(1- \frac{1}{d_X}\right)\;. \end{aligned}$$

(3.10)

Proof

For the first inequality, we use Hölder’s inequality (Lemma 3) with $r=t=4, \, s=2, \, A=C=I_{XZ} \otimes \rho _E^{1/4}$, and $B=\left(I_{XZ} \otimes \rho _E^{-1/4}\right) \left(\rho _{XZE}-U_X \rho _{ZE}\right) \left(I_{XZ} \otimes \rho _E^{-1/4}\right)$. This leads to

$$\begin{aligned} 2 \epsilon&= \left\Vert \rho _{XZE}-U_X \rho _{ZE} \right\Vert_1 \nonumber \\&=\left\Vert ABC \right\Vert_1 \nonumber \\&\le \left\Vert A^4 \right\Vert_1^{1/4} \left\Vert B^2 \right\Vert_1^{1/2} \left\Vert C^4 \right\Vert_1^{1/4} \nonumber \\&=\sqrt{d_X d_Z{{\,\mathrm{\text{ Tr }}\,}}\left((\rho _{XZE}-U_X \otimes \rho _{ZE} )\left(I_{XZ}\otimes \rho _E^{-1/2}\right)\right)^2 } \nonumber \\&=\sqrt{d_X d_Z\left(\Gamma _c(\rho _{XZE}|\rho _E) - \frac{1}{d_X}\Gamma _c(\rho _{ZE}|\rho _E) \right)}\; , \end{aligned}$$

(3.11)

where we used Eq. (3.4) in the last line. Squaring both sides and dividing by $d_X d_Z$, we get the desired inequality. For the second inequality, we use Lemma 4 to show that

$$\begin{aligned}&-\frac{1}{d_X}I_{XZE}\le \left(I_{XZ}\otimes \rho _E^{-\frac{1}{2}}\right)(\rho _{XZE}-U_X \otimes \rho _{ZE} )\left(I_{XZ}\otimes \rho _E^{-\frac{1}{2}}\right) \le \left(1-\frac{1}{d_X}\right) I_{XZE} \nonumber \\&\Rightarrow \left|\left(I_{XZ}\otimes \rho _E^{-1/2}\right)(\rho _{XZE}-U_X \otimes \rho _{ZE} )\left(I_{XZ}\otimes \rho _E^{-1/2}\right)\right| \le \left(1-\frac{1}{d_X}\right) I_{XZE}\;. \end{aligned}$$

(3.12)

Starting with Eq. (3.4), we have

$$\begin{aligned}&\Gamma _c(\rho _{XZE}|\rho _E) - \frac{1}{d_X}\Gamma _c(\rho _{ZE}|\rho _E)\nonumber \\&={{\,\mathrm{\text{ Tr }}\,}}\left((\rho _{XZE}-U_X \otimes \rho _{ZE} )\left(I_{XZ}\otimes \rho _E^{-1/2}\right)\right)^2 \nonumber \\&\le { {{\,\mathrm{\text{ Tr }}\,}}\left( \left|\rho _{XZE}-U_X \rho _{ZE}\right| \left|\left(I_{XZ}\otimes \rho _E^{-1/2}\right)(\rho _{XZE}-U_X \otimes \rho _{ZE} )\left(I_{XZ}\otimes \rho _E^{-1/2}\right) \right|\right)} \nonumber \\&\le { {{\,\mathrm{\text{ Tr }}\,}}\left( \left|\rho _{XZE}-U_X \rho _{ZE}\right| \left(1- \frac{1}{d_X}\right) I_{XZE} \right)} \nonumber \\&=2 \epsilon \left(1- \frac{1}{d_X}\right), \end{aligned}$$

(3.13)

where we used Eq. (3.12) on the fourth line.    $\square$

Now we restate and prove the non-uniform XOR lemma. The proof idea is to start from the trace distance of $X_0$ given X to uniform, apply Lemma 5 to get an upper bound in terms of the collision probability of $X_0$ given X, apply Eq. (3.4) and expand the square to express the collision probability of $X_0$ given X in terms of the collision probability of $X_0+\langle a,X\rangle$, and finally apply Lemma 5 again to get an upper bound in terms of the trace distance of $X_0+\langle a,X\rangle$ to uniform.

Lemma 1 (restated). Let p be a prime power, t an integer and $\epsilon \ge 0$. Let $\rho _{X_0XE}$ be a ccq state with $X_0 \in \mathbb {F}_p$ and $X=(X_1,\dots ,X_t)\in \mathbb {F}^t_p$. For all $a=(a_1,\dots ,a_t)\in \mathbb {F}^t_p$, define a random variable $Z=X_0+\langle a,X\rangle =X_0+\sum _{i=1}^t a_i X_i$. If for all a, $\frac{1}{2}\left\Vert \rho ^a_{ZE}-U_Z\otimes \rho _E \right\Vert_1\le \epsilon$, then

$$\begin{aligned} \frac{1}{2}\big \Vert \rho _{X_0XE}-U_{X_0}\otimes \rho _{XE}\big \Vert _1&\le \frac{p^{(t+1)/2}}{\sqrt{2}}\sqrt{\epsilon } \;. \end{aligned}$$

(3.14)

Proof

We start by relating the collision probability of Z and $X_0+\langle a,X\rangle$:

$$\begin{aligned}&\Gamma _c(\rho ^a_{ZE}|\rho _E)-\frac{1}{p} \nonumber \\&={{\,\mathrm{\text{ Tr }}\,}}\left[(\rho ^a_{ZE}-U_Z\rho _E)I_Z\otimes \rho _E^{-1/2} \right]^2 \nonumber \\&={{\,\mathrm{\text{ Tr }}\,}}\left[ \sum _z|z\rangle \langle z| \sum _{x,x_0}\left({\delta }\left(z-x_0-\langle a,x\rangle ,0\right)-\frac{1}{p} \right) \rho ^{x_0x}_E I_Z\rho _E^{-1/2} \right]^2 \nonumber \\&=\sum _z {{\,\mathrm{\text{ Tr }}\,}}\left[\sum _{x_0x} \left( {\delta }\left(z-x_0-\langle a,x\rangle ,0\right)-\frac{1}{p} \right) \rho ^{x_0x}_E \rho _E^{-1/2} \right]^2 \nonumber \\&=\sum _{z,x_0,x_0',x,x'} \left[ {\delta }\left(z-x_0-\langle a,x\rangle ,0\right) {\delta }\left(z-x_0'-\langle a,x'\rangle ,0\right)\right. \nonumber \\&\,\,\,\,\,\left. -\frac{2}{p} {\delta }\left(z-x_0-\langle a,x\rangle ,0\right)+\frac{1}{p^2} \right] {{\,\mathrm{\text{ Tr }}\,}}\left(\rho ^{x_0x}_E\rho _E^{-1/2}\rho ^{x_0'x'}_E\rho _E^{-1/2}\right) \nonumber \\&=\sum _{x_0,x_0',x,x'} \left[ {\delta }\left(x_0-x_0'+\langle a,x-x'\rangle ,0\right) -\frac{1}{p} \right]{{\,\mathrm{\text{ Tr }}\,}}\left(\rho ^{x_0x}_E\rho _E^{-1/2}\rho ^{x_0'x'}_E\rho _E^{-1/2} \right) \nonumber \\&=\sum _{x_0, x_0', x} \left( {\delta }\left(x_0-x_0',0\right) -\frac{1}{p} \right){{\,\mathrm{\text{ Tr }}\,}}\left(\rho ^{x_0x}_E\rho _E^{-1/2}\rho ^{x_0'x}_E\rho _E^{-1/2} \right) \nonumber \\&\,\,\,\,\,+ \sum _{x_0,x_0', x \ne x'} \left[ {\delta }\left(x_0-x_0'+\langle a,x-x'\rangle ,0\right) -\frac{1}{p} \right]{{\,\mathrm{\text{ Tr }}\,}}\left(\rho ^{x_0x}_E\rho _E^{-1/2}\rho ^{x_0'x'}_E\rho _E^{-1/2} \right) \nonumber \\&=\sum _{x_0, x} {{\,\mathrm{\text{ Tr }}\,}}\left(\rho ^{x_0x}_E\rho _E^{-1/2}\rho ^{x_0x}_E\rho _E^{-1/2} \right) - \frac{1}{p}\sum _{x_0, x_0', x} {{\,\mathrm{\text{ Tr }}\,}}\left(\rho ^{x_0x}_E\rho _E^{-1/2}\rho ^{x_0'x}_E\rho _E^{-1/2} \right) \nonumber \\&\,\,\,\,\,+\sum _{x_0,x_0', x \ne x'} \left[ {\delta }\left(x_0-x_0'+\langle a,x-x'\rangle ,0\right) -\frac{1}{p} \right]{{\,\mathrm{\text{ Tr }}\,}}\left(\rho ^{x_0x}_E\rho _E^{-1/2}\rho ^{x_0'x'}_E\rho _E^{-1/2} \right) \nonumber \\&=\Gamma _c(\rho _{X_0XE}|\rho _E) - \frac{1}{p}\Gamma _c(\rho _{XE}|\rho _E) \nonumber \\&\,\,\,\,\,+ \sum _{x_0,x_0', x \ne x'} \left[ {\delta }\left(x_0-x_0'+\langle a,x-x'\rangle ,0\right) -\frac{1}{p} \right]{{\,\mathrm{\text{ Tr }}\,}}\left(\rho ^{x_0x}_E\rho _E^{-1/2}\rho ^{x_0'x'}_E\rho _E^{-1/2} \right) . \end{aligned}$$

(3.15)

When we average over a, the last term vanishes,

$$\begin{aligned} \textsc {E}_{a}\left( \Gamma _c(\rho ^a_{ZE}|\rho _E)-\frac{1}{p} \right) = \Gamma _c(\rho _{X_0XE}|\rho _E) - \frac{1}{p}\Gamma _c(\rho _{XE}|\rho _E) \;. \end{aligned}$$

(3.16)

With the heavy work done, we put everything together and prove the lemma

$$\begin{aligned} \frac{\left\Vert \rho _{X_0XE}-U_{X_0}\rho _{XE} \right\Vert_1^2}{p^{t+1}}&\le \Gamma _c(\rho _{X_0XE}|\rho _E) - \frac{1}{p}\Gamma _c(\rho _{XE}|\rho _E) \nonumber \\&=\textsc {E}_{a}\left( \Gamma _c(\rho ^a_{ZE}|\rho _E)-\frac{1}{p} \right) \nonumber \\&\le 2\epsilon \, , \end{aligned}$$

(3.17)

where we used Lemma 5 one the first line, Eq. (3.16) on the second line, Lemma 5 and the assumption of the lemma on the third line. Multiplying both sides by $\frac{p^{t+1}}{2}$ and take a square root, we get the desired result:

$$\begin{aligned} \frac{1}{2}\left\Vert \rho _{X_0XE}-U_{X_0}\rho _{XE} \right\Vert_1&\le \frac{p^{(t+1)/2}}{\sqrt{2}}\sqrt{\epsilon }\;. \end{aligned}$$

(3.18)

$\square$

4 Quantum-Proof Non-malleable Extractor

In this section we introduce our non-malleable extractor and prove its security. The extractor was first considered by Li [27]. We use the symbol $\Vert$ for concatenation of strings, and for $a,b \in \mathbb {F}_p^n$ write $\langle a,b\rangle$ for the standard inner product over $\mathbb {F}_p^n$.

Definition 7

(Inner product-based non-malleable extractor). Let $p\ne 2$ be a prime. For any even integer n, define a function $\mathrm {nmExt}: \mathbb {F}_p^n \times \mathbb {F}_p^{n/2} \rightarrow \mathbb {F}_p$ by $\mathrm {nmExt}(X,Y) =\langle X, Y||Y^2\rangle$, where $Y^2$ is defined as in Sect. 2.1.

Theorem 1. Let $p\ne 2$ be a prime. Let n be an even integer. Then for any $\epsilon >0$ the function $\mathrm {nmExt}(X,Y)=\langle X, Y\Vert Y^2 \rangle$ is an $(\left(\frac{n}{2}+6\right){\log p} -1+4\log \frac{1}{\epsilon },\epsilon )$ quantum-proof non-malleable extractor.

The proof of Theorem 1 is based on a reduction showing that any successful attack for an adversary to $\mathrm {nmExt}$ leads to a good strategy for the players in a certain communication game, that we introduce next.

4.1 A Communication Game

Let $p\ne 2$ be a prime. Let n be an even integer, and $g:\mathbb {F}_{p}^{n/2} \times \mathbb {F}_{p}^{n/2} \rightarrow \mathbb {F}_p^n$ an arbitrary function such that for any $z\in \mathbb {F}_p^n$ there are at most two possible pairs $(y,y')$ such that $y\ne y'$ and $g(y,y')=z$. Consider the following communication game, called $\textsc {guess}(n,p,g)$, between two players Alice and Bob.

• 1. Bob receives $y\in \mathbb {F}_p^{n/2}$ from the referee.

• 2. Alice creates a cq state $\rho _{XE}$, where $X\in \mathbb {F}_p^n$, and sends the quantum register E to Bob.

• 3. Bob returns $y'\in \mathbb {F}_p^{n/2}$ and $b\in \mathbb {F}_p$.

The players win if and only if $b= \langle x ,g(y,y')\rangle$ and $y' \ne y$.

Note that Alice does not receive anything from the referee and is completely free in what state she wants to create, so it is easy for the players to win with probability 1 by creating a trivial state, e.g. $\rho _{XE}=|0\rangle \langle 0|\otimes |0\rangle \langle 0|$. Therefore we benchmark the success probability of a strategy by the min-entropy of Alice’s “input” X, conditioned on her message E to Bob. The following lemma bounds the players’ maximum success probability in this game over uniformly random input y and quantum measurements as a function of the min-entropy of Alice’s input X, conditioned on her message E to Bob.

Lemma 6

(Success probability of the communication game). Suppose there exists a communication protocol for Alice and Bob in $\textsc {guess}(n,p,g)$ that succeeds with probability at least $\frac{1}{p}+\epsilon$, on average over a uniformly random choice of input y to Bob. Then $H_{\mathrm {min}}(X|E)_\rho \le \frac{n}{2}\log p+1+2\log \frac{1}{\epsilon }$.

Proof

Let $\rho _{XE} = \sum _x {\left| {x}\right\rangle }\!{\left\langle {x}\right| }_X \otimes \rho _E^x$ be the cq state prepared by Alice. A strategy for Bob is a family of POVM $\{M_{y}^{y',b}\}_{y',b}$, indexed by $y\in \mathbb {F}_{p}^{n/2}$ and with outcomes $(y',b) \in \mathbb {F}_{p}^{n/2}\times \mathbb {F}_p$. We can assume that $\{M_{y}^{y',b}\}_{y',b}$ is projective, since Alice can send ancilla qubits along with $\rho$ and allow Bob to apply Naimark’s theorem to his POVM in order to obtain a projective measurement; this will change neither his success probability nor the min-entropy of Alice’s state. By definition, the players’ success probability in $\textsc {guess}(n,p,g)$ is

$$\begin{aligned} \frac{1}{p} + \epsilon \,=\, \sum _x \,p^{-\frac{n}{2}} \sum _{y} \sum _{y'} \sum _b\, {\delta }({b, \langle x, g(y,y')\rangle })\, \text{ Tr }\big ( M_{y}^{y',b} \,\rho _E^x\big )\;. \end{aligned}$$

(4.1)

For each $u\in \mathbb {F}_p$ let $A_{y,u}^{y'} = \sum _b \omega ^{ub} M_{y}^{y',b}$, where $\omega = e^{\frac{2i\pi }{p}}$. By inversion, $M_{y}^{y',b} = \frac{1}{p} \sum _u \omega ^{-ub} A_{y,u}^{y'}$. Replacing this into (4.1) we obtain

$$\begin{aligned} \frac{1}{p} + \epsilon&=\frac{1}{p}\sum _u \,p^{-\frac{n}{2}} \sum _{y} \sum _{y'} \sum _b\, {\delta }({b, \langle x, g(y,y')\rangle })\, \omega ^{-ub} \,\text{ Tr }\big ( A_{y,u}^{y'} \,\rho _E^x\big )\nonumber \\&\le \frac{1}{p} + \Big (1-\frac{1}{p}\Big )\max _{u\ne 0} \Big |p^{-\frac{n}{2}} \sum _{y} \sum _{y'} \sum _b\, {\delta }({b, \langle x, g(y,y')\rangle })\, \omega ^{-ub} \,\text{ Tr }\big ( A_{y,u}^{y'} \,\rho _E^x\big )\Big | \;, \end{aligned}$$

(4.2)

where for the second line we used that $\sum _{y'} A_{y,0}^{y'} = \sum _{y',b} M_y^{y',b} = I_E$.

Fix $u\ne 0$ that achieves the maximum in (4.2). For fixed y, define the map $T_{y,u}$ on $\mathcal {H}_E$ by

$$\begin{aligned} T_{y,u}: {\left| {\psi }\right\rangle } \mapsto \sum _{y'} {\left| {y'}\right\rangle } A_{y,u}^{y'} {\left| {\psi }\right\rangle }\;. \end{aligned}$$

(4.3)

$T_{y,u}$ has norm at most 1, since

$$T_{y,u}^\dag T_{y,u} =\sum _{y'} (A_{y,u}^{y'})^\dagger A_{y,u}^{y'}= \sum _{y'} \,\sum _b \Big (\,M_{y}^{y',b} \Big )^2 = I_E\;.$$

For the second equality we used that $\{M_{y}^{y',b}\}_{y',b}$ is projective. Therefore $T_{y,u}$ is a physical operation.

Consider the following guessing strategy for an adversary holding side information $\rho _E^x$ about x. The adversary first prepares a uniform superposition over y. Conditioned on y, it applies the map $T_{y,u}$. It computes $g(y,y')$ in an ancilla register, and erases $(y,y')$, except for one bit of information $r(y,y')\in \{0,1\}$, which specifies which pre-image $(y,y')$ is, given $g(y,y')$ (this is possible by the 2-to-1 assumption on g). The adversary applies a Fourier transform on the register containing $g(y,y')$, using $\omega _u = \omega ^{-u}$ as primitive p-th root of unity (this is possible since $u\ne 0$ and p is prime). It measures the result and outputs it as a guess for x. Formally, the transformation this implements is

$$\begin{aligned} {\left| {\psi }\right\rangle }&\mapsto p^{-\frac{n}{4}} \sum _y {\left| {y}\right\rangle } \sum _{y'} {\left| {y'}\right\rangle } A_{y,u}^{y'} {\left| {\psi }\right\rangle }\\&\mapsto p^{-\frac{n}{4}} \sum _{y,y'} {\left| {g(y,y')}\right\rangle } {\left| {r(y,y')}\right\rangle } A_{y,u}^{y'} {\left| {\psi }\right\rangle }\\&\mapsto \sum _v {\left| {v}\right\rangle } \Big (p^{-\frac{3n}{4}} \sum _{y,y'} \omega _u^{\langle v, g(y,y')\rangle } {\left| {r(y,y')}\right\rangle } A_{y,u}^{y'} \Big ){\left| {\psi }\right\rangle }\;. \end{aligned}$$

The adversary’s success probability in guessing $v=x$ on input $\rho _E^x$ is therefore

$$\begin{aligned} p_s&= \sum _x \,\text{ Tr }\Big ( \Big (p^{-\frac{3n}{4}} \sum _{y,y'} \omega _u^{\langle x, g(y,y')\rangle } {\left| {r(y,y')}\right\rangle }\otimes A_{y,u}^{y'} \Big ) \rho _E^x \nonumber \\&\cdot \Big (p^{-\frac{3n}{4}} \sum _{y,y'} \omega _u^{-\langle x, g(y,y')\rangle } {\left\langle {r(y,y')}\right| }\otimes (A_{y,u}^{y'})^\dagger \Big )\Big )\nonumber \\&= \frac{1}{p^{\frac{3n}{2}}} \sum _x\, \sum _{r\in \{0,1\}} \text{ Tr }\Big ( \Big (\sum _{y,y':\, r(y,y')=r} \omega _u^{\langle x, g(y,y')\rangle } A_{y,u}^{y'} \Big )^\dagger \nonumber \\&\cdot \Big (\sum _{y,y':\, r(y,y')=r} \omega _u^{\langle x, g(y,y')\rangle } A_{y,u}^{y'} \Big ) \rho _E^x \Big )\nonumber \\&\ge \frac{1}{p^{\frac{3n}{2}}} \sum _x \, \frac{1}{2}\,\text{ Tr }\Big ( \Big (\sum _{y,y'} \omega _u^{\langle x, g(y,y')\rangle } A_{y,u}^{y'} \Big )^\dagger \Big (\sum _{y,y'} \omega _u^{\langle x, g(y,y')\rangle } A_{y,u}^{y'} \Big ) \rho _E^x \Big )\; , \end{aligned}$$

(4.4)

where for the last line we used $\text{ Tr }(A^\dag A \rho )+\text{ Tr }(B^\dag B \rho ) \ge \frac{1}{2}\text{ Tr }((A+B)^\dag (A+B) \rho )$ if $\rho$ is positive semidefinite. Now, recall from (4.2) and our choice of u that

$$\begin{aligned} \epsilon&\le \,p^{-\frac{n}{2}} \Big |\sum _{x,y,y'} \, \omega ^{-u(\langle x, g(y,y')\rangle )} \,\text{ Tr }\big ( A_{y,u}^{y'} \,\rho _E^x\big )\Big |\nonumber \\&\le p^{-\frac{n}{2}}\Big (\sum _x \text{ Tr }(\rho _E^x)\Big )^{1/2} \nonumber \\&\cdot \Big ( \sum _x\, \text{ Tr }\Big ( \Big (\sum _{y,y'} \, \omega ^{-u(\langle x, g(y,y')\rangle )} \, A_{y,u}^{y'}\Big ) \,\rho _E^x\,\Big (\sum _{y,y'} \, \omega ^{-u(\langle x, g(y,y')\rangle )} \, A_{y,u}^{y'}\Big )^\dagger \Big )\Big )^{1/2}\;, \end{aligned}$$

(4.5)

where the inequality is Cauchy-Schwarz. Comparing (4.4) and (4.5) gives

$$ p_s \,\ge \, \frac{1}{2} p^{-\frac{n}{2}} \epsilon ^2\;.$$

We conclude using that by Lemma 2, $H_{\mathrm {min}}(X|E) \le -\log p_s$. $\square$

4.2 Proof of Theorem 1

In this section we give the proof of Theorem 1. Towards this we first prove a preliminary lemma showing that a certain function, based on the definition of $\mathrm {nmExt}$, has few collisions.

Lemma 7

Let $p \ne 2$ be a prime and n an even integer. For $a \in \mathbb {F}_{p}$ define a function $g_a:\mathbb {F}_{p}^{n/2} \times \mathbb {F}_{p}^{n/2} \rightarrow \mathbb {F}_{p}^n$ by

$$\begin{aligned} g_a(y,y') \,=\, y+ay'\Vert y^2+ay'^2\;, \end{aligned}$$

(4.6)

where $y^2$ is defined in Sect. 2.1. Then for any $a \in \mathbb {F}_{p}, a\ne 0$ and $z\in \mathbb {F}_p^n$ there are at most 2 distinct pairs $(y,y')$ such that $y'\ne y$ and $g_a(y,y')=z$.

Proof

We use the bijection defined in Sect. 2.1 to interpret y and $y'$ in $\mathbb {F}_{p^{n/2}}$. For $a\ne 0$, we fix an image $g_a=(c,d)$, where c, d are interpreted as elements of $\mathbb {F}_{p^{n/2}}$, and solve for $(y,y')$ in $\mathbb {F}_{p^{n/2}}\times \mathbb {F}_{p^{n/2}}$ satisfying

$$\begin{aligned} y+ay'&=c \;,\end{aligned}$$

(4.7)

$$\begin{aligned} y^2+ay'^2&=d\;. \end{aligned}$$

(4.8)

Using (4.7) to eliminate y we get

$$\begin{aligned}&(c-ay')^2+ay'^2=d \nonumber \\&\Rightarrow (a+a^2)y'^2+(-2ca)y'+(c^2-d)=0 \; . \end{aligned}$$

(4.9)

Since (4.9) is a quadratic equation, there are at most two solutions unless all coefficients are zero. Since $p\ne 2$, $-2\ne 0$. If all coefficients are zero, $-2\ne 0$, and $a \ne 0$, then $c=d=0,a=-1$, which implies $y' = y$ by (4.7) and contradicts our assumption. So there are at most two different $y'$ that can be mapped to (c, d). By (4.7) each $y'$ corresponds to a unique y, so there are at most two pre-images.    $\square$

We are ready to give the proof of Theorem 1. The proof depends on a simple lemma relating trace distance and guessing measurements, Lemma 8, which is stated and proved after the proof of the theorem.

Proof of Theorem 1. Let $k=\left(\frac{n}{2}+6\right)\log p-1+4\log \frac{1}{\epsilon }$ and $\rho _{XE} \in \mathrm {D}(\mathbb {C}^{p^{n }} \otimes \mathcal {H}_E)$ an $(n \log p,k)$-source. Fix a CPTP map $\mathrm {Adv}: \mathrm {L}(\mathbb {C}^{p^{n/2}}\otimes \mathcal {H}_E) \rightarrow \mathrm {L}(\mathbb {C}^{p^{n/2}} \otimes \mathcal {H}_{E'})$ with no fixed points, and define $\sigma _{\mathrm {nmExt}(X,Y) \mathrm {nmExt}(X,Y') YY' E'}$ as in Definition 5. Given the definition of $\mathrm {nmExt}$, to prove the theorem we need to show that

$$\begin{aligned} (\langle X,Y\Vert Y^2\rangle ,\langle X,Y'\Vert Y'^2\rangle ,Y',Y,E')_\sigma \approx _\epsilon (U_{\mathbb {F}_p},\langle X,Y'\Vert Y'^2\rangle ,Y',Y,E')_\sigma \;. \end{aligned}$$

(4.10)

Applying the XOR lemma, Lemma 1, with $X_0 =\langle X,Y||Y^2\rangle$, $X = \langle X,Y'||Y'^2\rangle$, $E = (Y',Y,E')$ and $t=1$, (4.10) will follow once it is shown that

$$\begin{aligned}&(\langle X,Y||Y^2\rangle +a \langle X,Y'\Vert Y'^2\rangle ,Y',Y,E')_\sigma \approx _{\frac{2\epsilon ^2}{p^2}} (U_{\mathbb {F}_p},Y',Y,E')_\sigma \;, \end{aligned}$$

(4.11)

for all $a\in \mathbb {F}_p$. For $a=0$,  (4.11) follows from the fact that inner product is a quantum-proof two source extractor, which can be shown by the combination of Theorem 5.3 of [10] and Lemma 1 in [24]. For non-zero $a\in \mathbb {F}_p$, recall the function $g_a: \mathbb {F}_{p}^{n/2} \times \mathbb {F}_{p}^{n/2} \rightarrow \mathbb {F}_p^n$ defined in (4.6). Lemma 7 shows that for any $a\ne 0$, the restriction of $g_a$ to $\{(y,y'):\,y\ne y'\}$ is at most 2-to-1, and $y \ne y'$ is ensured by the fact that $\mathrm {Adv}$ has no fixed points. We establish (4.11) by contradiction. Assume thus that

$$\begin{aligned} (\langle X,g_a(Y,Y')\rangle ,Y',Y,E' )_\sigma \approx _{\frac{2\epsilon ^2}{p^2}}( U_{\mathbb {F}_p},Y',Y,E' )_\sigma \end{aligned}$$

(4.12)

does not hold, for some non-zero $a\in \mathbb {F}_p$. Fix such an a and write $g_a$ for g. From Lemma 8 it follows that there exists a POVM measurement $\{M^z\}_{z\in \mathbb {F}_p}$ on $\sigma _{Y'YE'}$ such that

$$\begin{aligned} \sum _{z\in \mathbb {F}_p}\, \text{ Tr }\big ( M^z \sigma ^z_{YY'E} \big ) \,\ge \,\frac{1}{p}+ \frac{2\epsilon ^2}{p^3}\;, \end{aligned}$$

(4.13)

where $\sigma ^z_{YY'E}$ is the reduced density of $\sigma$ on $YY'E$ conditioned on $\langle X,g(Y,Y')\rangle =z$. To conclude the proof of the theorem we show that the adversary’s map $\mathrm {Adv}$ and the POVM $\{M^z\}$ can be combined to give a “successful” strategy for the players in the communication game introduced in Sect. 4.1. To see this, consider the state $\rho _{XE}$ that is instantiated as the source for the extractor; by definition $H_{\mathrm {min}}(X|E)_\rho = k = \left(\frac{n}{2}+6\right)\log p-1+4\log \frac{1}{\epsilon }$. In the third step of the game, Bob applies the map $\mathrm {Adv}$ to the registers Y and E containing his input Y and the state sent by Alice, and measures to obtain an outcome $Y'$. He then applies the measurement $\{M^z\}$ on his registers $(Y,Y',E)$ to obtain a value $b=z\in \mathbb {F}_p$ that he provides as his output in the game. By (4.13) it follows that this strategy succeeds in the game with probability at least $\frac{1}{p}+ \frac{2\epsilon ^2}{p^3}$, which by Lemma 6 implies $H_{\mathrm {min}}(X|E) \le \frac{n}{2}\log p+1+2\log \frac{p^3}{2\epsilon ^2}$, contradicting our choice of k. This proves (4.11) and thus the theorem.    $\square$

The following lemma is used in the proof of the theorem.

Lemma 8

Let $\rho _{XE} = \sum _{x} {\left| {x}\right\rangle }\!{\left\langle {x}\right| }\otimes \rho _E^x$ be such that

$$\frac{1}{2}\Vert (X,E)-(U,E)\Vert _1\,=\,\frac{1}{2}\big \Vert \rho _{XE}- U_X \otimes \rho _E \big \Vert _1 \,= \, \epsilon \;,$$

where $U_X$ is the totally mixed state on X and $\rho _E = \sum _x \rho _E^x$. Then there exists a POVM $\{M_x\}$ on $\rho _E$ such that

$$\sum _{x} \text{ Tr }(M_x\rho _E^x) = \frac{1}{d_X} + \frac{\epsilon }{d_X}\;.$$

Proof

Since $\rho _{XE}$ is a cq state, $\Vert \rho _{XE}- U_X \otimes \rho _E\Vert _1 = \sum _x \Vert \rho _E^x - \frac{1}{d_X}\rho _E\Vert _1$. For each x, let $M'_x$ be the projector onto the positive eigenvalues of $\rho _E^x - \frac{1}{d_X}\rho _E$, so

$$\begin{aligned} \sum _x \text{ Tr }( M'_x(\rho _E^x - \frac{1}{d_X}\rho _E)) = \frac{1}{2}\sum _x \Vert \rho _E^x -\frac{1}{d_X}\rho _E\Vert _1\;. \end{aligned}$$

(4.14)

Let $M' = \sum _x M'_x$ and $M_x =\frac{1}{d_X}( M'_x + (I_E-\frac{1}{d_X} M'))$. Then $M_x\ge 0$ and $\sum _x M_x =\frac{1}{d_X}(M'+d_XI_E-M') = I_E$. Moreover,

$$\begin{aligned} \sum _x \text{ Tr }(M_x\rho _E^x)&=\sum _x \text{ Tr }\left[ \frac{1}{d_X}( M'_x + (I_E-\frac{1}{d_X} M')) \rho _E^x \right] \\&= \frac{1}{d_X} \left[\sum _x \left(\text{ Tr }( M'_x \rho _E^x )\right)+ \text{ Tr }\left((I_E-\frac{1}{d_X} M') \rho _E \right)\right] \\&= \frac{1}{d_X} +\frac{1}{d_X} \sum _x \Big (\text{ Tr }(M'_x \rho _E^x) - \frac{1}{d_X}\text{ Tr }(M'_x \rho _E) \Big )\\&= \frac{1}{d_X} + \frac{1}{d_X} \Big (\sum _x \text{ Tr }\big ( M'_x (\rho _E^x - \frac{1}{d_X}\rho _E)\big )\Big )\\&= \frac{1}{d_X} + \frac{1}{2d_X} \sum _x \Big \Vert \rho _E^x - \frac{1}{d_X}\rho _E\Big \Vert _1 \end{aligned}$$

by (4.14).    $\square$

5 Privacy Amplification

Dodis and Wichs [19] introduced a framework for constructing a two-message privacy amplification protocol from any non-malleable extractor. In [14] it is shown that the same framework, when instantiated with a quantum-proof non-malleable extractor $\mathrm {nmExt}$ as defined in Definition 5, leads to a protocol that is secure against active quantum adversaries. In Sect. 5.1 we recall the Dodis-Wichs protocol, and state the security guarantees that follow by plugging in our non-malleable extractor construction. The guarantees follows from the quantum extension of the Dodis-Wichs results in [14]; since that work has not been published we include their results regarding the Dodis-Wichs protocol in Appendix A.

In Sect. 5.2 we show that a different protocol for privacy amplification due to Dodis et al. [16], whose main advantage is of being a one-round protocol, is also quantum-proof. The construction and analysis of the protocol of [16] is simple, with the drawback of a large entropy loss.

We start with the definition of a quantum-secure privacy amplification protocol against active adversaries. A privacy amplification protocol $(P_A, P_B)$ is defined as follows. The protocol is executed by two parties Alice and Bob sharing a secret $X\in \{0,1\}^n$, whose actions are described by $P_A$, $P_B$ respectively.⁷ In addition there is an active, computationally unbounded adversary Eve, who might have some quantum side information E correlated with X but satisfying $H_{\mathrm {min}}(X|E)_{\rho } \ge k$, where $\rho _{XE}$ denotes the initial state at beginning of the protocol.

Informally, the goal for the protocol is that whenever a party (Alice or Bob) does not reject, the key R output by this party is random and statistically independent of Eve’s view. Moreover, if both parties do not reject, they must output the same keys $R_A=R_B$ with overwhelming probability.

More formally, we assume that Eve is in full control of the communication channel between Alice and Bob, and can arbitrarily insert, delete, reorder or modify messages sent by Alice and Bob to each other. At the end of the protocol, Alice outputs a key $R_A\in \{0,1\}^m \cup \{\perp \}$, where $\perp$ is a special symbol indicating rejection. Similarly, Bob outputs a key $R_B \in \{0,1\}^m \cup \{\perp \}$. The following definition generalizes the classical definition in [17].

Definition 8

Let k, m be integer and $\epsilon \ge 0$. A privacy amplification protocol $(P_A, P_B)$ is a $(k, m, \epsilon )$-privacy amplification protocol secure against active quantum adversaries if it satisfies the following properties for any initial state $\rho _{XE}$ such that $H_{\mathrm {min}}(X|E)_\rho \ge k$, and where $\sigma$ be the joint state of Alice, Bob, and Eve at the end of the protocol:

• 1. Correctness. If the adversary does not interfere with the protocol, then $\Pr [R_A=R_B \wedge ~ R_A\ne \perp \wedge ~ R_B\ne \perp ]=1$.

• 2. Robustness. This property comes in two flavors. The first is pre-application robustness, which states that even in the presence of an active adversary, $\Pr [R_A \ne R_B \wedge ~ R_A \ne \perp \wedge ~ R_B \ne \perp ]\le \epsilon$. The second is post-application robustness, which is defined similarly, except the adversary is additionally given the key $R_A$ that is the result of the interaction $(P_A,P_E)$, and the key $R_B$ that results from the interaction $(P_E,P_B)$, where $P_E$ denotes the adversary’s actions in its interaction with Alice and Bob.

• 3. Extraction. Given a string $r\in \{0,1\}^m\cup \{\perp \}$, let $\mathsf {purify}(r)$ be a random variable on m-bit strings that is deterministically equal to $\perp$ if $r=\perp$, and is otherwise uniformly distributed. Let V denotes the transcript of an execution of the protocol execution, and $\rho _{E'}$ the final quantum state possessed by Eve. Then the following should hold:

  $$(R_A, V, E')_\sigma \approx _{\epsilon } (\mathsf {purify}(R_A), V, E')_\sigma ~~~~\text{ and }~~~~ (R_B, V, E')_\sigma \approx _{\epsilon } (\mathsf {purify}(R_B), V, E')_\sigma \;.$$

  In other words, whenever a party does not reject, the party’s key is indistinguishable from a fresh random string to the adversary.

The quantity $k-m$ is called the entropy loss.

5.1 Dodis-Wichs Protocol with Non-malleable Extractor

Here we first recall the Dodis-Wichs protocol for privacy amplification (hereafter called Protocol DW), which is summarized in Fig. 1, and the required security definitions, taken from [14]. We then state the result obtained by instantiating the protocol with the quantum-proof non-malleable extractor from Theorem 1.

Fig. 1.

The Dodis-Wichs privacy amplification protocol.

Aside from the use of a strong quantum-proof extractor (Definition 3) and a quantum-proof non-malleable extractor (Definition 5), the protocol relies on an information-theoretically secure one-time message authentication codes, or $\textsc {MAC}$. This security notion is defined as follows.

Definition 9

A function $\textsc {MAC}:\{0,\ldots ,d_Z-1\}\times \{0,1\}^d \rightarrow \{0,1\}^t$ is an $\epsilon _\textsc {MAC}$-information-theoretically secure one-time message authentication code if for any function $\mathcal {A}:\{0,1\}^d \times \{0,1\}^t \rightarrow \{0,1\}^d\times \{0,1\}^t$ it holds that for all $m\in \{0,1\}^d$

$$\mathop {\Pr }\limits _{k\leftarrow {U_{Z}}}\big [ (\textsc {MAC}(k,m') = \sigma ' ) \, \wedge \, (m'\ne m) : (m',\sigma ') \leftarrow \mathcal {A}(m,\textsc {MAC}(k,m))\big ] \le \epsilon _\textsc {MAC}.$$

Efficient constructions of $\textsc {MAC}$ satisfying the conditions of Definition 9 are known. The following proposition summarizes some parameters that are achievable using a construction based on polynomial evaluation.

Proposition 1

(Proposition 1 in [34]). For any $\epsilon _\textsc {MAC}>0$, integer $d > 0$, $d_Z \ge \frac{d^2}{\epsilon _\textsc {MAC}^2}$, there exists an efficient family of $\epsilon _\textsc {MAC}$-information-theoretically secure one-time message authentication codes

$$\{\textsc {MAC}:\{0,\ldots ,d_Z-1\} \times \{0,1\}^d \rightarrow \{0,1\}^t\}_{d\in \mathbb {N}}$$

with $t\le \log d + \log (1/\epsilon _\textsc {MAC})$.

The correctness and security requirements for the protocol are natural extensions of the classical case (see Definition 18 in [19]). Informally, the adversary has the following control over the outcome of the protocol. First, it possess initial quantum side information E about the weak secret X shared by Alice and Bob. That is, it has a choice of a cq source $\rho _{XE}$, under the condition that $H_{\mathrm {min}}(X|E)$ is sufficiently large. Second, the adversary may intercept and modify any of the messages exchanged. In Protocol DW there are only two messages exchanged, $Y_A$ from Alice to Bob and $(Y_B,\sigma )$ from Bob to Alice. To each of these messages the adversary may apply an arbitrary transformation, that may depend on its side information E. We model the two possible attacks, one for each message, as CPTP maps $T_1 : \mathrm {L}(\mathcal {H}_Y \otimes \mathcal {H}_E) \rightarrow \mathrm {L}(\mathcal {H}_Y \otimes \mathcal {H}_{E'})$ and $T_2 : \mathrm {L}(\mathbb {C}^{2^{d_2}} \otimes \mathcal {H}_{2^{t}}\otimes \mathcal {H}_{E'}) \rightarrow \mathrm {L}(\mathbb {C}^{2^{d_2}} \otimes \mathbb {C}^{2^{t}} \otimes \mathcal {H}_{E''})$, where $\mathcal {H}$ denotes the Hilbert space associated with system E. Note that we may always assume that $\mathcal {H}$ is large enough for the adversary to keep a local copy of the messages it sees, if it so desires.

The following result on the security of protocol DW is shown in [14]. We include the proof in Appendix A.

Theorem 3

Let $k,t,d_Z$ and $\epsilon _\textsc {MAC},\epsilon _\mathrm {Ext},\epsilon _\mathrm {nmExt}$ be parameters of Protocol DW, as specified in Fig. 1. Let $\mathrm {nmExt}$ be a $(k,\epsilon _\mathrm {nmExt})$ quantum-proof non-malleable extractor, $\mathrm {Ext}$ a strong $(k-\log d_Z-\log (1/\epsilon _\mathrm {Ext}),\epsilon _\mathrm {Ext})$ quantum-proof extractor, and $\textsc {MAC}$ an $\epsilon _\textsc {MAC}$-information-theoretically secure one-time message authentication code. Then for any active attack $(\rho _{XE},T_1,T_2)$ such that $H_{\mathrm {min}}(X|E)_\rho \ge k$, the DW privacy amplification protocol described in Fig. 1 is $(k,m,\epsilon )$-secure as defined in Definition 8 with $\epsilon = O(\epsilon _\mathrm {Ext}+ \epsilon _{\mathrm {nmExt}} + \epsilon _\textsc {MAC})$.

Combined with Theorem 1 stating the security of our construction of a quantum-proof non-malleable extractor, Theorem 3 provides a means to obtain privacy amplification protocol secure against active attacks for a range of parameters. Due to the limitations of our non-malleable extractor we are only able to extract from sources whose entropy rate is at least $\frac{1}{2}$. This is a typical setting in the case of quantum key distribution, where the initial min-entropy satisfies $H_{\mathrm {min}}(X|E) \ge \alpha \log d_X$ for some constant $\alpha$ which depends on the protocol and the noise tolerance, but is generally larger than 3 / 4. Specifically, we obtain the following:

Corollary 1

For any $\epsilon > 0$, there exists a constant $c > 0$, such that the following holds. For any active attack $(\rho _{XE},T_1,T_2)$ such that $H_{\mathrm {min}}(X|E)_\rho = k \ge \frac{1}{2} \log d_X + c \cdot {\log (1/\epsilon )}$, there is an $O(\epsilon )$-secure DW protocol that outputs a key of length $m = k - O({\log (1/\epsilon )})$.

Proof

Let p be a prime and n a positive integer such that $\log p = \Theta ({\log (1/\epsilon )})$ and $d_X = p^n$. Let $d_Y = p^{n/2}$, and $d_Z = p$. Also, let $d_2 = O(\log d_X)$, $m = k - O({\log (1/\epsilon )})$, and $t = O({\log (1/\epsilon )})$. We instantiate Theorem 3 with the following.

• Let $\mathrm {Ext}:\{0,\ldots ,d_X-1\}\times \{0,1\}^{d_2} \rightarrow \{0,1\}^m$ be the $(k - O(\log (1/\epsilon )),\epsilon )$ strong quantum-proof extractor from Theorem 2.

• Let $\mathrm {nmExt}:\{0,\ldots ,d_X-1\}\times \{0,,\ldots ,d_Y-1\} \rightarrow \{0,\ldots ,d_Z-1\}$ be the $(\frac{1}{2} \cdot \log d_X + O({\log (1/\epsilon )}),\epsilon )$ non-malleable extractor from Theorem 1.

• Let $\textsc {MAC}:\{0,\ldots ,d_Z-1\} \times \{0,1\}^{d_2} \rightarrow \{0,1\}^t$ be the one-time $\epsilon$-information-theoretically secure message authentication code from Proposition 1.

The result follows.    $\square$

5.2 One-Round Privacy Amplification Protocol

In this section we show that the one-round protocol of Dodis et al. [16] is also quantum-proof. This protocol has significantly higher entropy loss, $(n/2) + \log (1/\epsilon )$, than the DW protocol we presented in the previous section.

Fig. 2.

The one-round privacy amplification protocol from  [16].

Theorem 4

For any integer n and $k > n/2$, and any $\epsilon >0$, the protocol in Fig. 2 is a one-round $(k,m,\epsilon )$-quantum secure privacy amplification protocol with post-application robustness and entropy loss $k-m = (n/2)+ \log (1/\epsilon )$.

Proof

Correctness and extraction follow as in the classical proof by observing that $\mathrm {Ext}(X, Y) = YX_1+X_2$ is a quantum-proof extractor since $h_Y(X_1,X_2) = YX_1+X_2$ is a family of universal hash function, which is shown to be a quantum-proof strong extractor in [36]. For robustness, the classical proof does not generalize directly. We prove post-application robustness as follows.

We proceed by contradiction. Suppose post-application robustness is violated, i.e. $\Pr [R_A \ne R_B \wedge ~ R_A \ne \perp \wedge ~ R_B \ne \perp ]> \epsilon$. Then there is an initial state $\rho _{XE}$ with $H_{\mathrm {min}}(X|E)_\rho \ge k$ and a CPTP map $T: \mathrm {L}(\mathcal {H}_Y \otimes \mathcal {H}_W \otimes \mathcal {H}_{R_A} \otimes \mathcal {H}_E) \rightarrow \mathrm {L}(\mathcal {H}_Y \otimes \mathcal {H}_W \otimes \mathcal {H}_{E'})$ that can be applied by an adversary Eve to produce a modified message that is accepted by Bob with probability greater than $\epsilon$. Note that T has $R_A$ as input since we consider post-application robustness. Let $(Y',W',E')=T(Y,W,R_A,E)$. If post-application robustness is violated, then $\Pr [ W'=[Y' X_1+X_2]_1^v] > \epsilon$.

Consider the following communication game: Alice has access to a cq-state $\rho _{XE}$. Alice samples a uniformly random Y, computes $W=[Y X_1+X_2]_1^v$, $R_A = [Y X_1+X_2]_{v+1}^{n/2}$, and sends E, Y, W, and $R_A$ to Bob. They win if Bob guesses X correctly from E, Y, W, and $R_A$. Using the map T introduced above, Bob can execute the following strategy. First, apply T on Alice’s message to generate a guess $(Y',W')$. Second, guess a uniformly random $R'_B$. Third, use $Y,Y', (W,R_A) = Y X_1+X_2,$ and $(W',R'_B) = Y' X_1+X_2$ to solve for a unique $X=(X_1,X_2)$. Note that Bob succeeds if the guesses $(Y',W')$ and $R'_B$ in the first two steps are both correct (i.e., $(W',R'_B) = Y' X_1+X_2$), which has probability greater than $\epsilon \cdot 2^{- ((n/2) - v)}$. On the other hand, we can upper bound the winning probability of the communication game using the min entropy assumption $H(X|E)_\rho \ge k$. Since Y is independent of X and the length of $(W,R_A)$ is n / 2, $H_{\mathrm {min}}(X|E,Y,W)_\rho \ge k - (n/2)$. Thus the winning probability is less than $2^{-(k-(n/2))}$. Putting the two calculations together we have

$$\epsilon \cdot 2^{- ((n/2) - v)} \le \Pr [ \text{ Bob } \text{ wins } ] \le 2^{-(k-(n/2))},$$

which implies $v < n-k-\log (1/\epsilon )$, a contradiction.    $\square$

A The Dodis-Wichs Protocol

In this appendix we reproduce the proof of Theorem 3, taken from [14].

Proof of Theorem 3. Let an active attack on Protocol DW be specified by

• A cq state $\rho _{XE} \in \mathrm {D}(\mathcal {H}_X \otimes \mathcal {H}_E)$ such that $H_{\mathrm {min}}(X|E)_\rho \ge k$;

• A CPTP map $T_1 : \mathrm {L}(\mathcal {H}_Y \otimes \mathcal {H}_E) \rightarrow \mathrm {L}(\mathcal {H}_Y \otimes \mathcal {H}_{E'})$ whose output on the first registered is systematically decohered in the computational basis; formally, for any $\rho _{YE}$, $T_1(\rho _{YE}) = \sum _{y} (|y\rangle \langle y|_Y \otimes \mathop {\mathrm {Id}}\nolimits _E)T_1(\rho _{YE}) (|y\rangle \langle y|_Y$

  $\otimes \mathop {\mathrm {Id}}\nolimits _E)$;

• A CPTP map $T_2 : \mathrm {L}(\mathbb {C}^{2^{d_2}} \otimes \mathbb {C}^{2^{t}}\otimes \mathcal {H}_{E'}) \rightarrow \mathrm {L}(\mathbb {C}^{2^{d_2}} \otimes \mathbb {C}^{2^{t}} \otimes \mathcal {H}_{E''})$.

Given an active attack $(\rho _{XE},T_1,T_2)$ we instantiate random variables $Y_A,Z,Y'_A, Y_B,Z',$ $\sigma ,Y'_B,\sigma '$ and $R_A,R_B$ in the obvious way, as defined in the protocol and taking into account the maps $T_1$ and $T_2$, applied successively to determine $Y'_A$ and $(Y'_B,\sigma ')$.

The correctness of the protocol is clear.

To show robustness, let $\sigma _{ Y'_A Y_A X E'}$ denote the joint state of $Y'_A$, $Y_A$ (which represents a local copy of $Y_A$ kept by Alice), X, and Eve’s registers after her first map $T_1$ has been applied. Further decompose $\rho$ as a sum of sub-normalized densities $\sigma ^=_{Y'_A Y_A X E'}$, corresponding to conditioning on $Y'_A=Y_A$, and $\sigma ^\perp _{Y'_A Y_A X E'}$, corresponding to conditioning on $Y'_A\ne Y_A$.

Conditioned on $Y'_A=Y_A$, by definition of a $\textsc {MAC}$ the probability that $(Y'_B,W')\ne (Y_B,W)$ and Alice reaches the $\textsc {KeyConfirmed}$ state is at most $\epsilon _{\textsc {MAC}}$. If $(Y'_B,W') = (Y_B,W)$ then $R_A=R_B$, so that in this case robustness holds with error at most $\epsilon _\textsc {MAC}$.

Now suppose $Y'_A \ne Y_A$. Consider a modified adversary $\mathrm {Adv}'$ that keeps a copy of $Y_A$, applies the map $T_1$, and if $Y'_A=Y_A$ replaces $Y'_A$ with a uniformly random string that is distinct from $Y_A$. This adversary implements a CPTP map $T'_1$ that has no fixed point. By the assumption that $\mathrm {nmExt}$ is a quantum-proof non-malleable extractor,

$$\begin{aligned} \sigma '_{\mathrm {nmExt}(X,Y_A) \mathrm {nmExt}(X,Y'_A) Y_AY'_A E'} \approx _{\epsilon _\mathrm {nmExt}} U_m \otimes {\sigma '}_{\mathrm {nmExt}(X,Y'_A) Y_A Y'_AE'}, \end{aligned}$$

(A.1)

where here $Y'_AE'$ is defined as the output system of the map $T'_1$ implemented by $\mathrm {Adv}'$. Conditioned on $Y_A \ne Y'_A$ the maps $T_1$ and $T'_1$ are identical, thus it follows from (A.1) and the definition of $\rho ^{\perp }$ that

$$\sigma ^{\perp }_{\mathrm {nmExt}(X,Y_A) \mathrm {nmExt}(X,Y'_A) Y_AY'_A E'} \approx _{\epsilon _\mathrm {nmExt}} U_m \otimes \sigma ^{\perp }_{\mathrm {nmExt}(X,Y'_A) Y_A Y'_AE'},$$

where now the states are sub-normalized. Since $Z'= \mathrm {nmExt}(X,Y'_A)$ this means that the key used by Alice to verify the signature in Step 3. of Protocol DW is (up to statistical distance $\epsilon _\mathrm {nmExt}$) uniform and independent of the key used by Bob to make the MAC. By the security of MAC, the probability for Alice to reach the $\textsc {KeyConfirmed}$ state in this case is at most $\epsilon _{\mathrm {nmExt}}+\epsilon _{\textsc {MAC}}$. Adding both parts together, $\Pr (R_A \notin \{R_B,\perp \})\le \epsilon _{\mathrm {nmExt}}+2\epsilon _{\textsc {MAC}}$. Since $R_B$ is never $\bot$, this implies the robustness property.

For the extraction property, it is sufficient to show that $(R_B,V,E)\approx _{\epsilon } (U_m,V,E)$ since then key extraction property follows from the robustness and the fact that $R_B$ is never $\bot$. We have that $R_B=\mathrm {Ext}(X,Y_B)$ is close to uniform given $V=Y_AY_BW$ and $E'$, and we need to establish two properties: first, independence between X and $Y_B$ given $Y_AZ'E'$ and second, that the source has enough entropy conditioned on $Y_AZ'E'$. Regarding the first property, observe that conditioned on $Y_AZ'$, X and $Y_B$ are independent given $E'$. Regarding the source entropy, by the chain rule for the (smooth) min-entropy [37], it follows that $H_{\mathrm {min}}^{\epsilon _\mathrm {Ext}}(X|Y_AZ'E') \ge k-\log d_Z-c\log (1/\epsilon _\mathrm {Ext})$ for some constant $c>0$. Note that

$$\begin{aligned} \big \Vert (R_B,V,E')_\sigma -(U_m,V,E')_\sigma \big \Vert _1&\le \big \Vert (R_B,Y_A,Y_B,Z',E')_\sigma -(U_m,Y_A,Y_B,Z',E')_\sigma \big \Vert _1 , \end{aligned}$$

which follows since W is a deterministic function $Y_B$ and $Z'$. Using that $\mathrm {Ext}$ is a strong quantum-proof extractor, we conclude that $(R_B,V,E)\approx _{\epsilon } (U_m,V,E)$, as long as $\epsilon$ is such that $\epsilon > \epsilon _\mathrm {Ext}$.    $\square$